CS320 Programming Assignment 2

The object of this assignment is to implement the Huffman compression algorithm discussed in the greedy algorithms notes and in section 4.8 of the book. The algorithm, uses a priority queue to store intermediate trees.

You must use your own priority queue code from PA 1.

One way to represent the trees is by tuples, as a tuple can have tuples as constituents. This representation is compact and elegant. However, if you prefer a different implementation of the prefix trees, you are welcome to do that.

If you use tuples to represent the trees, here is a python skeleton code tup.py, which reads a set of "frequency,letter" pairs, eg from file in, and plays with tuples to understand how they compare and what is (not) a tuple.

Your Huffman code should be called huff.py. It reads a file of frequency letter pairs such as in and produces a Huffman encoding of the letters in the input file. For the example input:

45,a 13,b 12,c 16,d 9,e 5,f

a valid output of your program is:

huff: {'a': '0', 'c': '100', 'b': '101', 'e': '1101', 'd': '111', 'f': '1100'}