image University of Washington Computer Science & Engineering
  CSE 421,  Su '07:  Assignment #3, Due: Wednesday, July 18, 2007
  CSE Home   About Us    Search    Contact Info 

Problems:

  1. [10 points] Prof. Flashbulb proposed the following greedy algorithm for solving the all-interval scheduling problem (aka interval coloring, section 4.1): apply the greedy algorithm for interval scheduling from the earlier part of section 4.1; give all of those intervals one color, remove them from consideration, and recursively apply the same method to the resulting reduced set of intervals. Does this method does give an optimal solution to the problem? Either prove it or give a simple counterexample and explain why your counter example is a counter example.

  2. [10 points] A quick look at the algorithm on page 124 for the all-intervals scheduling problem suggests an O(n2) time bound: an outer loop for j = 1, ..., n, and an implicit inner loop "for each interval Ii" that also seems to need order n time.

    1. Give a slightly more detailed description of an implementation of this algorithm that will take only O(dn) time, where d is the depth of the problem instance (pg 123). (For your timing analysis, ignore the Theta(n log n) time for the initial step that sorts the intervals by start time.)
    2. If d is small, the above method typically will be much faster than the simple O(n2) analysis suggests. Show, however, that it is not faster in the worst case. I.e., show that there are instances where it takes time Omega(n2). [Note that to show a lower bound like this, it's not good enough to show one bad example; you really need to show that there are infinitely many bad examples, for larger and larger values of n.]
    3. Give a more clever implementation of the algorithm whose running time is O(n log n), (independent of depth) and justify this time bound. [Hint: use a priority queue.]

  3. [10 points] Chapter 4, Page 190, Problem 5.

  4. [10 points] Chapter 4, Page 191, Problem 6.

  5. [10 points] Chapter 4, Page 194, Problem 13.

  6. [10 points] Chapter 4, Page 198, Problem 19.

  7. [10 points]

    1. Simulate the Huffman tree algorithm on the input alphabet a, b, c, d, e with frequencies .15, .30, .50, .02, .03, resp. Show the intermediate "trees" built by the algorithm, as well as the final tree.
    2. What will be the total length in bits of the compressed text built from a sequence of 100 letters having the above frequencies using the Huffman code you calculated?
    3. Suppose I tell you that the frequencies of a and b are .15, .30, resp, as above, but I don't tell you the other frequencies. I can quickly tell (e.g., without running the full Huffman algorithm) that the Huffman code for this data is not the one shown in figure 4.16 (a) (pg 168). Explain how.

  8. [10 points] Suppose you break a file into 8 bit characters and find that all 256 combinations are present, with the most frequent occuring less that twice as often as the least frequent. Prove that the Huffman code for this data will not result in a shorter file.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX