Homework #4

- Exercise 3.3 (p 402) in the book
- Exercise 3.9 (p 405) in the book
- Prove that rounding down of (log-base 2 of n)+1 is equal to the rounding up of log-base 2 of (n+1).
- 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