# Consider The Problem Of Rightjustifying A Paragraph The Paragraph Contains

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’ 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’ 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.