Remarks: In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation.

1. Question 1: The Random Quicksort algorithm works as follows. We assume that the numbers are pairwise different.

(a) If the array has one element or is empty return the array

(b) Otherwise choose a number at random from A[1], A[2], . . . , A[n]. This number is

called a pivot. Let x be the value of the chosen entry

(c) Create an array AS of all elements smaller than x, and AL the elements that are

larger than x

(d) Recursively sort AS and AL and return AS,x,AL.

Let B[1], B[2], . . . , B[n] be the array A sorted, namely B[i] is the ith smallest number in A. Let Xij be the random variable that has value of 1 if B[i] and B[j] are compared, and has value 0 otherwise. Let T be the number of comparisons in Random Quicksort

(a) Show that T = ni=1 j>i Xij.

(b) Show that if B[p] for p < i or p > j is chosen as pivot this does not change the

probability that B[i] and B[j] will be compared.

(c) Show that if the first element chosen as pivot among B[i], B[i+1], . . . , B[j] is A[p]

for i < p < j, then Xij = 0 (B[i] and B[j] are not compared).

(d) Show that the probability that B[i], B[j] are compared is 2/(j i + 1),

(e) Show that E(T) = ni=1 j>i 2/(j i + 1).

(f) Show that for i = 1, j>1 P(B[1] and B[i] are compared) = 2(1 + 1/2 + 1/3 +

1/4 + . . . 1/n) = 2 ln n + (1).

(g) ShowthatE(T)2nlnn+O(n).