Problem
Analyze a randomized algorithm that finds an item close enough to the median item of a set S = {a1, . . . , an} of n distinct numbers. Specifically, the algorithm finds an item ai such that at least n/4 items are smaller than ai and at least n/4 items are greater than ai.
Algorithm : Randomized Approximate Median (S)
• Select an item ai ∈ S uniformly at random
• rank=1
• for j=1 to n do
• if aj • end if
• end for
• if ⌊n/4⌋ < rank ≤ ⌊3n/4⌋ then return ai
• else return error
• end if
1. What kind of randomized algorithm is Randomized Approximate Median(S) and why?
2. What is the running time of this algorithm?
3. What is the success probability of this algorithm?
4. Show how you can amplify (improve) the success probability of Randomized Approximate Median(S) to over 99% by running several independent executions of the algorithm. You should analyze the success probability and the running time of the resulting algorithm.