!)

(c) Trace the execution of Huffmans algorithm for the following set of frequencies: a : 4, b : 75, c : 1, d : 2, e : 5. Show what the tree will look like at the end ((if you prefer, you can just draw the tree by hand with paper and pencil instead of with a word processor). Also show what will be the encoding for cbadbe with this code.

(d) Consider the Zvi-Lempel ZIP compression algorithm applied to the text: catinthecatinhat

Show what will be the representation for the repeated codes (you just have to show the final representation where the compressed representation is being used, you dont have to show the normal representation part, you dont have to show the trace or intermediate steps). you can assume

we are following exactly the same protocol described in class and in the handout.

the repeating representation is used only if the length is at least 3.

the 8-bit for pointers and 4-bit for length option is used here.

we are using the decimal notation

you dont have to calculate the number of bits