Assignment 3: Greedy Algorithms and Huffman Data Compression
CSE 417: Algorithms and Computational Complexity
The University of Washington, Seattle, Winter 2013
The reading for this assignment is Chapter 4 of Algorithm Design by Kleinberg and Tardos. Do this assignment independently, without the use of online resources or collaboration.
Due Monday, February 4. Submit your answers as hardcopy at the beginning of class.
 
  1. The Cheapest Edge (10 points). In Kleinberg and Tardos, Chapter 4, Exercise 1.
     
  2. Matters of Squaring (10 points). In Kleinberg and Tardos, Chapter 4, Exercise 2.
     
  3. Getting One's Trucks in Order (15 points). In Kleinberg and Tardos, Chapter 4, Exercise 3.
     
  4. A Trying Triathlon (20 points). In Kleinberg and Tardos, Chapter 4, Exercise 6.
     
  5. Security at the Lowest Cost (20 points). In Kleinberg and Tardos, Chapter 4, Exercise 14.
     
  6. Optimal Coding for Data Compression (25 points).
    (a) Use the algorithm on p.172 to construct a Huffman code for the following alphabet and probabilities, showing your final Huffman tree, as well as the intermediate trees involved in its construction. 
    e: 0.35
f: 0.05
g: 0.2
h: 0.02
i: 0.1
j: 0.03
k: 0.25

    (b) Give the encoding for the following 15-byte string: "eggiffeghijikee"

    (c) How many bytes does the encoding require, including a starting byte that gives the length of the string?


    7.  
Updates and Corrections: Removed the spurious string beginning with "xyz" in the Huffman tree problem (Jan. 30). Any additional changes or important clarifications to the assignment will be posted here.