Tutorial 2 for CSC 310

For this week's tutorial, I'd like you to do things about Huffman
codes.

For starters, you can get them to find the Huffman code for a source
with five symbols, having probabilities

  1/2, 1/4, 1/8, 1/16, 1/16

The result should be codewords of 0, 10, 110, 1110, 1111, if you
follow the algorithm in the most obvious way.  You should draw this as
a tree on the board as well.  

At this point, you can compute the expected codeword length for this
code, compare to the entropy (they should be the same), and ask them
why the code achieves the entropy bound in this case (answer: the
probabilities are all integer powers of two, so the codewords are all
the lengths that they "ought" to be).

You can then ask them what other instantaneous codes for this source
are optimal.  They should be able to get several by changing the
arbitrary choices made in the Huffman code algorithm (namely, the
choice between using bit 0 and bit 1, and (in other contexts) the way
of breaking ties among probabililities).  For instance, another
instantaneous code for this source is 1, 01, 000, 0010, 0011.

You can then go on to ask whether there are other optimal codes that
are uniquely decodeable but not instantaneous.  There are, since you
can, for instance, just reverse all the codewords of the Huffman code.
This gives a code that can be decoded by scanning the bits in reverse
order once they've all been received.

Now you can ask them how much the probabilities can be changed while
leaving the Huffman code unchanged.  For instance, if we change the
last two probabilities to 3/32 and 1/32, will the Huffman code change?
Will the expected code length change?  Will the expected code length
still be equal to the entropy?  What other changes to the
probabilities could be made without changing the Huffman code?

As a sort of opposite example, consider a source with eight symbols
having probabilities 1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8.  What is
the Huffman code for this source?  As may be obvious, it will have
codewords that are all three bits long.  Is the expected codeword
length equal to the entropy?  (Yes, fairly obviously.)  How much can
these probabilities vary without changing the Huffman code?  For the
answer to this, you can read Question 2 of Assignment 1 from CSC 310
two years ago, and the solution to it, which can be found on that
year's course web page, linked to from the bottom of this year's
course web page.