An alphabet contains symbols A, B, C, D, E, F. The frequencies of the symbols are 35%, 20%, 15%, 15%, 8%, and 7%, respectively. We know that the Huffman algorithm always outputs an optimal prefix code. However, this code is not always unique (obviously we can, e.g., switch 0s and 1s and get a different code - but, for some inputs, there are two optimal prefix codes that are more substantially different). For the purposes of this exercise, we consider two Huffman codes to be different if there exists a symbol for which one of the codes assigns a shorter codeword than the other code.

Trace the Huffman algorithm and construct two different Huffman codes for the above input.

Compute the expected number of bits per symbol (i.e., the expected codeword length) for both codes.