2
$\begingroup$

Yes, this is homework. I need help knowing how to begin this problem:

Let A be an algorithm that finds the kth largest of n elements by a sequence of comparisons. Prove by contradiction that A collects enough information to determine which elements are greater than the kth largest and which elements are less than it. In other words, you can partition the set around the kth largest element without making more comparisons.

I'm not looking for an answer. I am confused about how to even begin this question, it's the last one on my homework and tried searching quite a bit for similar situations. My fellow students seem confused as well. I also asked the professor but he lived up to his reputation for being quite cryptic. I actually found someone else's answer online searching, which I will provide here:

Call the majority element x and say it appears i > b n/2 c times. Each time x is encountered, it is either pushed on the stack or an element (different from x) is popped off the stack. There are n − i < I elements different from x. Assume x is not on the stack at the end of the procedure. Then, each of the I elements of x must have either popped another element off the stack, or been popped off by another element. However, there are only n − i < I other elements, so this is a contradiction. Therefore, x must be on the stack at the end of the procedure

I don't remotely even know if that's correct, and I don't understand it.

How do I even approach this question? It seems like the initial question needs more information about the algorithm for me to be able to answer it. Or maybe there is an underlying implication to "sequence of comparisons" that I'm missing. I don't understand how to begin without a specific algorithm provided. None of his example problems he has done in class and none I've found in the book are like this. All the other problems have specific algorithms. I feel like maybe I am missing an important concept?

$\endgroup$

marked as duplicate by David Richerby, Yuval Filmus algorithms Jun 7 '17 at 13:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Your question seems to be i-th order statistic of n element array, that is, i-th smallest element. Do you have access to any book? Cormen's book (chapter 9) has a good explanation of this topic. Your question is too general to answer it. $\endgroup$ – fade2black Jun 6 '17 at 0:15
  • $\begingroup$ You are given say, 10-element array (possibly unsorted), and asked to find, say, 3d smallest element. The simple approach is to sort it and then return the third element. But this is overkill requiring O(nlog(n)) time on average. Since we are interested in only the third element we could solve it faster, in O(n) time on average. This is the idea. $\endgroup$ – fade2black Jun 6 '17 at 0:24