Math 480, Fall 2016, Assignment 8

Do not imagine that mathematics is hard and crabbed and repulsive to commmon sense. It is merely the etherealization of common sense.

- Lord Kelvin

Carefully define the following terms, then give one example and one non-example of each:

1. Average word length (of an encoding scheme).

Carefully describe the following algorithms:

1. Huffman's algorithm.

Carefully state the following theorems (you need not prove them):

1. Theorem concerning the output of Huffman's algorithm (i.e. the output is what kind of code?).
2. Theorem concerning optimality of Huffman codes

Solve the following problems:

1. Section 4.3, problems 1 and 4.

--------------------End of assignment--------------------