Huffman Coding From a Teaching Perspective

Data Structures and Topics Used in the Assignment

To ensure that students are adequately prepared to do this assignment, ideally you will have covered the topics listed below. You can, however, skip some of these if you provide classes/modules to students that can be used while insulating students from specific knowledge of how the classes work.

Providing infrastructure for Students

At a minimum, you will need to provide the classes used to read and write 1 bit (or n-bits) at a time. A few simple example programs are typically enough to show students how these bit-stream classes are used. We call the classes ibstream  for input bit stream and obstream  for output bit stream.

Optionally, you can provide design ideas and/or implementations of some classes for students to use. When we originally gave this assignment we asked students to implement a priority queue class. Since most books provide some implementation, and often an efficient heap-based implementation, we now provide the priority queue class and expect students to use it without understanding (for the purposes of this assignment) its implementation.

We have given this assignment with no suggestions for any design or problem decomposition and with some minimal hints for some classes that might be useful. We stress that code that's used in the huff/unhuff (compression/uncompression) programs should not be duplicated in two different source code files, but factored into common functions or classes that are used by both programs.

We also have provided several kinds of solutions (currently these are only available in C++).

Owen L. Astrachan
Last modified: Thu Feb 04 13:45:35 PST 1999