Math 480, Fall 2016, Assignment 6

I tell them that if they will occupy themselves with the study of mathematics, they will find in it the best remedy against the lusts of the flesh.

- Thomas Mann, The Magic Mountain

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

1. Encoding function.
2. Ambiguous (encoding function).
3. VDR (Valid Decoder-Reader).
4. Uniquely decodable (encoding function).
5. Encoding scheme.
6. Left-to-right reading.
7. Prefix-free code.

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

1. Theorem concerning existence of VDRs for encoding schemes.
2. Theorem concerning unique decodability (and giving an efficient VDR) for prefix-free codes.

Solve the following problems:

1. Section 4.1, problems 4, 5, and 6.

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