Problem: We say that an item $x$ is of rank $m$ if there are $m$ items in the set less than $x$. Design a randomized algorithm to find all of the items in a set of size $n$ with rank greater than $\frac{n}{16}$ with probability of failure $\frac{1}{1024}$.

I had this problem on my final yesterday and it completely stumped me. I don't even know how to begin. Any hints would be appreciated.

  • 2
    $\begingroup$ Could you report the exact text of the exercise? As you've written it, there is a trivial deterministic linear-time algorithm (select the n/16-th element, partition around that). $\endgroup$ – quicksort Dec 23 '17 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.