[10 points]
In class, someone proposed the following greedy algorithm for
solving the allinterval 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.
[10 points]
A quick look at the algorithm on page 124 for the allintervals
scheduling problem suggests an O(n^{2}) time bound: an
outer loop for j = 1, ..., n, and an implicit inner loop "for each
interval I_{i}" that also seems to need order n time.
 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.)
 If d is small, the above method typically will be much faster
than the simple O(n^{2}) 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(n^{2}). [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.]
 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.]
[10 points] Chapter 4, Page 190, Problem 5.
[10 points] Chapter 4, Page 191, Problem 6.
[10 points]
 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.
 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?
 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.


Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 981952350
(206) 5431695 voice, (206) 5432969 FAX
