CS 3158: Design and Analysis of Algorithms
Homework 5: Due Friday, 7th August 1998

1. (10 points) Exercise 17.3-1, page 344 of the text.
2. (10 points) Let be the frequencies of n characters to be encoded. Prove that there exists an optimal prefix code tree for these n characters in which the leaves corresponding to and appear as siblings of an internal node at maximum depth.
3. (15 points) Let be n positive integer inputs to the Huffman tree construction algorithm. How small can be so that the tree constructed by this algorithm is completely skewed (i.e., some root-to-leaf path in the tree has n vertices)? Prove your answer. What are the values of ?
4. (10 points) Exercise 16.1-1, page 308 of the text.
5. (20 points) Problem 16-3, page 325 of the text. Assume that only the operations Insert, Delete and Replace are used.
6. (15 points) Exercise 23.1-6, page 468 of the text.

• About this document ...