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). Explain your answers.