Due Date: Monday Mar. 1
- 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).
Explain your answers.
- 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