Consider the problem of right-justifying a paragraph. The paragraph contains a sequence of words w1, w2, . . . , wN of length a1, a2, . . . , aN, which we wish to break into lines of length L. Words are separated by blanks whose ideal length is b (millimeters), but blanks can stretch or shrink as necessary (but must be > 0), so that a line wiwi+1 . . . wj has length exactly L. However, for each blank b we charge |b' − b| ugliness points. The exception to this is the last line, for which we charge only if b' < b (in other words, we charge only for shrinking), since the last line does not need to be justified. Thus, if bi is the length of the blank between ai and ai+1, then the ugliness of setting any line (but the last) wiwi+1 . . . wj for j > i is Σj−1k=I |bk − b| = (j − i)|b' − b|, where b' is the average size of a blank on this line. This is true of the last line only if b' < b, otherwise the last line is not ugly at all.

a. Give a dynamic programming algorithm to find the least ugly setting of w1, w2, . . . , wN into lines of length L.

b. Give the time and space complexities for your algorithm (as a function of the number of words, N).

c. Consider the special case where we are using a fixed-width font, and assume the optimal value of b is 1 (space). In this case, no shrinking of blanks is allowed, since the next smallest blank space would be 0. Give a linear-time algorithm to generate the least ugly setting for this case.