Problem: Huffman Encoding
Consider alphabet composed of eight symbols {A, B, C, D, E, F, G, H}
1. If every symbol occurs with equal frequency, what is the entropy of this distribution? What is the Huffman encoding? Argue that the Huffman encoding is optimal.
2. Assume that the symbols occur in increasing frequency (i.e fa<= fb <= ...<=fh). Generate a set of possible unequal frequencies or counts for each symbol that generate the same Huffman encoding tree as the uniform frequency case, but try to maximize the difference between fh and fa. Show the choices yield a uniform Huffman encoding tree. ( Hint think about the priority queue of symbol frequencies and how the Huffman encoding algorithm must execute to yield the specified encoding tree).
3. Generate a system of inequalities for the frequencies {fa,....,fh} that would guarantee a uniform Huffman encoding tree.