CIS 725
Homework 2
Due 10/1 at the beginning of class. I'm not terribly picky about
formatting -- handwritten, typed, whatever. As long as it's legible
and reasonably well organized.
Do one of the following two problems.
Problem 1
Implement Huffman's coding algorithm. Your program should take as input a
list of symbols and their probabilities, and produce a table of symbols
and their codewords. You may use any language you like. You should also
use some reasonable style/coding convention; if you're uncertain about
that you can find some general guidelines here.
You may design the input/output however you like. 90% of the points will
be based on correctness/efficiency/style, and 10% on "bonus" stuff -- I'll
give you points if you want to add features, or implement a GUI, or other
fun things.
Turn in your source code as well as screenshots or output dumps of your
program running.
Problem 2
Huffman codes are provably optimal (in a certain sense); we have not
discussed whether Shannon codes are optimal in the same sense.
Investigate: is there a set of symbols and probabilities for which
Huffman performs better (i.e. has a lower average bits/symbol) than
Shannon? If so, show it; if you think not, explain how you reached this
conclusion.