image University of Washington Computer Science & Engineering
  CSE 417,  Wi '07:  Assignment #3, Due: Friday, Jan. 26, 2007
  CSE Home   About Us    Search    Contact Info 

Midterm:

Friday, 2/2.

Reading:

Chapter 4 (omit 4.7, 4.9).

Problems:

For problems that say "give an algorithm", I want both a high-level description of the algorithm (see the faq page for some discussion about the level of detail expected), and a brief paragraph explaining why your algorithm is correct. (This doesn't have to be very formal, but do try to make it convincing, say, to other students in the class.)

  1. [10 points] In class, someone 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. Show that this method does not give an optimal solution to the problem by giving a counterexample. (Keep it simple; 4 to 6 intervals should suffice.) 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]

    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.

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