Please look at the handout regarding assigments on the class web site before submitting your solutions.

1. Suppose that if the constant 5 is replaced by the constant 3 in the algorithm of Section 9.3 of Cormen et al. Is the proof that the algorithm has worst-case linear time complexity still valid?

2. The observation underlying Exercise 9.1-1 of Cormen et al is that when the winner of a tournament is removed, it's realtively easy to find the second-place finisher. This observation can be extended to define a sorting algorithm, as follows:

     Given a positive integer k,
       divide the input sequence into 2k groups
       sort each group recursively
       play a tournament among the smallest elements of each group
       repeatedly replace the tournament winner with its successor in its sorted group
         and replay the comparisons involving this winner to get the next winner
         (using a sentinel when a group is exhausted)

   What is the worst-case time complexity of this algorithm?

3. Use dynamic programming to find the optimal way of multiplying a chain of matrices of respective sizes 15x10, 10x20, 20x5, 5x40, and 40x10, given that the cost of finding the product of a pxq matrix and a qxr matrix is pqr, and that the cost to be minimized (as in Cormen et al, Section 15.2) is the sum of the costs of all of the products of pairs of matrices that are computed in the overall multiplication. Note that here subproblems correspond to substrings of the input chain, and smaller problems correspond to smaller substrings.

4. Fill in the details of the proof outline given in class for the Huffman algorithm. The outline may be found at the end of one of the slides (in either MS Word format or text format on the class web site. Specifically,
   • say why O must have two leaves that are siblings at the lowest level
   • say why O is still optimal after the transformation of step 2
   • justify the claims of steps 4, 5, and 6