Discovery of Huffman Codes

Abstract

The invention of Huffman codes is a great story that demonstrates that students can do better than professors. In 1951, David Huffman was a student in an electrical engineering course taught by professor Robert Fano. In the course, Fano offered students a choice of taking a final exam or writing a term paper. Huffman did not want to take the final exam, so he opted to work on the term paper. The topic of the paper was to find the most efficient (optimal) code. What Fano did not tell his students was the fact that it was an open problem, and that he was working on the problem himself. Huffman spent a lot of time on the problem and was ready to give up when the solution suddenly came to him. The code that Huffman discovered was optimal, that is, it had the lowest possible average message length. 

This student project uses excerpts from the individual works of Fano and Huffman, where they present their respective encodings. Both Fano and Huffman used greedy strategies to find the codes. However, Fano’s greedy algorithm would not always produce an optimal code, while Huffman’s greedy algorithm would always find an optimal solution. The purpose of the project is for students to learn greedy algorithms, prefix-free codes, Huffman encoding, binary tree representations of codes, and the basics of information theory (unit and amount of information). The project demonstrates that a greedy strategy could be applied in different ways to the same problem, sometimes producing an optimal solution and sometimes not. This project is designed for a junior-level Data Structures and Algorithms course.