Next: 4.9.2 Comparison of Hash Tables and Binary Search Trees
Up: 4.9 Programming Assignments
Previous: 4.9 Programming Assignments
- 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,
Assume the alphabets as 1, 2, 3, ..., without loss of generality.
- 8 .2 .02 .3 .05 .03 .15 .22 .03
- 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.