REMINDERS: All problem sets are to be typeset using
LaTeX and submitted on paper.
All problems from CLRS are from the 3rd edition.
- Do problem 16.1-4 from CLRS. Prove your algorithm correct and analyze its running time.
- Returning to problem 3 of last week's problem set
- Suppose we define the badness of a paragraph to be the sum of the
badnesses of the lines in the paragraph, not including the final line.
Describe a greedy algorithm that computes the minimum possible paragraph badness,
given the words
w1, w2,...,wn
and the maximum line length M. As usual, prove your
algorithm correct and analyze its running time.
- Suppose we define the badness of a paragraph to be the maximum of the
badnesses of the lines in the paragraph, not including the final line.
Is the resulting problem amenable to a greedy solution? If so, provide (and prove and analyze)
a suitable algorithm. If not, give an example showing how the greedy solution fails.
- Do problem 24.1-1 from CLRS.
- Do problem 24.3-2 from CLRS.