REMINDERS: All problem sets are to be typeset using LaTeX and submitted on paper. All problems from CLRS are from the 3rd edition.
For this assignment, please submit a paper version of your write-up as usual, but also submit the same document as a PDF via Moodle. For problem #2, submit your discussion of your running time tests as a part of your paper and PDF submissions, and submit your source code only via Moodle.
For the problem described in 15-2 on page 405 of CLRS, provide an efficient algorithm, prove its correctness, and provide an analysis of its running time.
Implement your longest-palindrome-finding algorithm from the previous problem in either Python or Java. Your program should be invokeable using either the command "python longestpalindrome.py string" or "java LongestPalindrome string".
In addition, collect and present running time data. Test your program on enough different lengths of strings to provide reasonable support your running time analysis of your algorithm.
As noted above, you should submit your source code via Moodle.
Consider problem 15-4 on pages 405-406 of CLRS. This problem concerns a paragraph of words w1, w2,...,wn with lengths l1, l2,...,ln, to be printed in lines of maximum length M (where M ≥ lk ∀ k), without using hyphenation to break words across two lines. The badness of a line wi, wi+1,...,wj is defined as M - j + i - ∑k=ij lk. That is, the badness is the number of space characters added to the end of the line to get to a total of M. We will define the badness of a paragraph as the sum of the squares of the badnesses of its lines, not counting the last line.
Here's an illustration using a quote from Donald Knuth, showing two different layouts with M = 28:
Your job is to describe an efficient dynamic programming algorithm to lay out a paragraph to minimize its badness. Prove your algorithm correct, and analyze its running time.