# Fundamental Algorithms Homework #4

Due Date: Monday Mar. 1

1. Exercise 3.3 (p 402) in the book
2. Exercise 3.9 (p 405) in the book
3. Prove that rounding down of (log-base 2 of n)+1 is equal to the rounding up of log-base 2 of (n+1).
4. Assume that n is a power of 2. Consider the algorithm below.
Assume that the numbers are not equal to one another. Given a list of n numbers; in the first round pair the numbers 2 by 2 then compare the numbers in each pair; in successive rounds pair the winners of the previous round 2 by 2 then compare the numbers in each pair; the winner in the last round is the biggest number in the list. (This is in fact the way tournaments are conducted).
• a. Show that the algorithm is correct.
• b. How many rounds are there?
• c. How many comparisons does the algorithm use?
• d. How many comparisons involve the biggest number?
• e. How would you augment the algorithm so that it finds also the number second to the biggest?
• f. How many additional comparisons would be needed for (e) above