Due: April 25, 2001, 11AM by email

This programming assignment will give you practice with heaps and an interesting algorithm - Huffman Coding - for compressing a text file using variable length codes.

The assignment has three parts:

1. Read a text input file of letters, and compute their frequencies.To build the tree, follow the handout and algorithm described in class. Note

2. Construct the binary tree representing the Huffman Code for this text, and print the resulting code.

3. Encode the message using this code and output the string of 0's and 1's that correspond to it. How much compression do you get?

that this algorithm makes heavy use of heaps.

Addendum (as noted by Josh
in the mailing list): output your characters and the corresponding Huffman
code, in order of most to least frequent. Test the

compression you get by encoding
the Gettysburg address text (from the last assignment) and computing the
savings. (Do not output the encoded message).