1. A ?le contains only colons, spaces, newlines, commas, and digits in the following frequency: colon (100), space (605), newline (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217). Construct the Huffman code.
2. Part of the encoded ?le must be a header indicating the Huffman code. Give a method for constructing the header of size at most O(N) (in addition to the symbols), where N is the number of symbols.
3. Complete the proof that Huffman's algorithm generates an optimal pre?x code.
4. Show that if the symbols are sorted by frequency, Huffman's algorithm can be implemented in linear time.
5. Write a program to implement ?le compression (and uncompression) using Huffman's algorithm.