Consider the problem of nding the largest and second largest elements from a set of n elements.

a) Give a simple iterative algorithm that takes no more than 2n 3 comparisons. b) Give a divide and conquer algorithm and show that it takes 3n 2 2 comparisons when n is a power of 2.

c) Show how you can nd both these elements in n + logn2 comparisons in the worst case (assume n is a power of 2). (Hint: See hint in problem 2.7.)

Here is 2.7:

Show that the celebrity problem can be solved by using 3n logn 3 questions (assume that n is a power of 2). (Hint: Group people into pairs similar to a knockout tournament, e.g., Wimbledon tennis tournament.)

Here is the answer to this 2.7:

As in the hint, rst group the n people in pairs of two i.e., we will have n/2 pairs. This will be the rst round. For each pair, say (x,y), ask one question if x knows y. This question will eliminate one person i.e., he/she cant be a celebrity. The winner from this pair will be one who is not eliminated. All the winners from this round there will be n/2 of them will advance to the next round. In the next round, again repeat the process group into n/4 pairs and question n/4 will advance to the next round. This is exactly how a knockout tournament is organized. Finally, there will be one champion (the winner in the nal round) after logn rounds; because each round eliminates half the number of persons. How many questions were asked before the champion is found ? This can 2 be computed by summing up the questions asked in each round: n/2 + n/4 + n/8 ++ 1 = n(1/2 + 1/22 + 1/23 ++ 1/2logn) The series inside the parantheses is a geometric sum: Hence that can be evaluated as 1/2 + 1/22 + 1/23 ++ 1/2logn = (1/2)(11/2log n) 1/2 = 11/n. Hence, n/2+n/4+n/8++1 = n(1/2+1/22+1/23++1/2logn) = n(11/n) = n1. If there is a celebrity he /she has to be the champion. This has to be checked by asking whether all others know the champion and whether the champion knows anybody else. This takes no more than 2n2 questions. However, note that we dont have to ask the same question (in one way) with the person who lost to the winner. This saves logn questions. Hence, the total number of questions is n1 + 2n2logn = 3nlogn3.