COS 226 Homework #5
Due: Tuesday, March 29, 2005

Written Exercises

Follow the instructions on the assignments page on how and when to turn these in.  Point values of each problem are shown in brackets.  Be sure to also complete the programming part of this assignment, including the program report.

1. [4] Draw the R-way existence trie that results when you insert the following keys into an initially empty trie.  Use the alphabet of ten digits (R = 10).  Draw all of the null links.  You may assume that all keys are of the same length.
   
       351 652 893 353 351
    
2. [4] Draw the TST that results when you insert the following keys into an initially empty trie. Draw all of the null links. You may assume that all keys are of the same length.
   
       351 652 893 353 351
    
3. Consider source symbols drawn from the alphabet {a, b, c, d, e, f, g} with the following probabilities:
   
       p_a = 0.49
       p_b = 0.26
       p_c = 0.12
       p_d = 0.04
       p_e = 0.04
       p_f = 0.03
       p_g = 0.02
   
   
   1. [2] Compute the entropy of this distribution of symbols.
   2. [4] Find a Huffman code for this source, and compute its average code length.
   3. [2] Use your Huffman code to encode the text:  gaba.
   4. [4] Find a Shannon-Fano code for this source, and compute its average code length.