[Randomized Algorithms]. Consider the following (unusual) randomized algorithm for nding the maximum among a set of numbers X (there is a context where such approach is useful).

For simplicity, we assume that the numbers in X are all dierent. random(X) returns one of the elements in X uniformly at random (each is equally likely).

(a) Obtain a recurrence for the expected number of recursive calls in the execution of FindMax. (You need to take into account in the recurrence that x is chosen at random; you shouldnt simply assume that x is in the middle on the average.)

(b) Solve the recurrence obtained in the previous part.

(c) Obtain a recurrence for the expected running time of Find-Max.

(Same remark as

above.)

(d) Solve the recurrence obtained in the previous part.

(e) What is the probability that Find-Max(X) compares the i-th largest and the j-th largest items in X ? Here, we mean the i-th and j-th largest in the linear order (1-st largest is the max, n-th largest is the min). We also mean the probability over all the execution of the algorithm, including recursive calls.

(Randomized Algorithms, 30 points). Consider the following (unusual) randomized al- gorithm for finding the maximum among a set of numbers X (there is a context where such approach is useful). FIND-MAX (X) 1.n+ X 2.x* + random(X) 3.Y + 4. for each I e X do 5. if r*