Assignment 3

Due Monday, February 4th

Directions
For problems that say "give an algorithm", give both a high-level description and an explanation of why your algorithm is correct.

1. Chapter 4, Page 188, Problem 1 [10 points]

2. Chapter 4, Page 189, Problem 3 [15 points]

3. Chapter 4, Page 190, Problem 4 [15 points]

4. Chapter 4, Page 191, Problem 6 [20 points]

5. [20 points]

(This question is based on a student's submission for the extra credit on homework 1.) A family of n individuals are to be seated at a round table. If individuals i and j are sitting next to each other at the table, let ageGap(i,j) be the difference in ages between i and j. We want to find a way to seat the entire family at the table, while minimizing the sum of the all the ageGaps.

This can be considered to be an instance of the travelling salesman problem (TSP). There is a graph of n nodes, one for each individual, with edges between the nodes that correspond to the differences in age. We want to find a cycle that visits all the nodes, with the smallest total length.

Even though TSP is very hard to solve in general, this is a special case of the problem that can be solved quickly with a greedy algorithm. Explain why this version of the problem is easier than the general definition of TSP, give an algorithm to solve it requiring O(n log n) time, and explain why your algorithm is correct.

6. [20 points]

1. Simulate the Huffman tree algorithm on the input alphabet a, b, c, d, e with frequencies .15, .30, .50, .02, .03, resp. Show the intermediate "trees" built by the algorithm, as well as the final tree.
2. What will be the total length in bits of the compressed text built from a sequence of 100 letters having the above frequencies using the Huffman code you calculated?
3. Suppose I tell you that the frequencies of a and b are .15, .30, resp, as above, but I don't tell you the other frequencies. I can quickly tell (e.g., without running the full Huffman algorithm) that the Huffman code for this data is not the one shown in figure 4.16 (a) (pg 168). Explain how.

Extra Credit

1. Concrete Application (2 points)