CSCC73H3 Quiz: huffman
2 Mar 2017
School
Department
Course
Professor
Document Summary
We prove the correctness of hu man"s algorithm by induction on the number of symbols n in the alphabet. The base case, n = 2 is obvious because the only possibility (that is not obviously suboptimal) is a code where both codewords are one bit long, which is what hu man"s algorithm produces in this case. Suppose that the algorithm produces an optimal tree for alphabets with n 1 2 symbols and their associated frequencies. We will prove that it produces an optimal tree for alphabets with n symbols and their associated frequences. Let be an alphabet with n symbols, and f (a) be the frequency for each a . Let h be the tree produced by hu man"s algorithm for , f . We must prove that h is optimal for this input. By the algorithm, there are two symbols of minimum frequency (according to f ) that are siblings in h; let these symbols be x and y.
