next up previous
Next: 4.9.2 Comparison of Hash Tables and Binary Search Trees Up: 4.9 Programming Assignments Previous: 4.9 Programming Assignments

4.9.1 Huffman Coding

Problem: Given a set of alphabets and their relative frequencies, find the Huffman binary code using binary trees and an optimal ternary code using ternary trees.

Reading: Read pages 94-102 of "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman.

Input: The number of alphabets and relative frequencies of those, for example,

8 .2 .02 .3 .05 .03 .15 .22 .03
Assume the alphabets as 1, 2, 3, ..., without loss of generality.

Output: For each alphabet, print the Huffman binary code and an optimal ternary code. Also print the average length of code.

Data structures: For binary trees, use the data structures suggested by Aho, Hopcroft, and Ullman. For ternary trees, use similar data structures based on leftmostchild-right sibling representation with nodes organized into cellspace.

Programming language: Use C or C++or Java. Best practices in programming should be adhered to.