Every web browser and word processor needs a way of breaking English paragraphs into lines at word boundaries that is both fast and looks good. Some systems even have ways of hyphenating words to make good line breaks, but let us ignore that complication here. Say that the width of each line on a computer screen or browser window is M characters, and we are given a list, 

W = (W₁, W₂,...,W_n), 

of n words forming a paragraph that we wish to display, where the word, W_i, has length, L_i. The word wrapping problem is to break W into lines of length at most M in a way that minimizes a total cost penalizing the wasted space. The cost of breaking a single line to hold the words W_i, W_i+1,...,W_j , has the following cost: 

assuming this cost is nonnegative. If this cost is negative, then we instead set C(i, j) = +∞, to show that the set of words from W_i to W_j doesn’t fit on a single line. In addition, if this cost is positive, but j = n, then we set C(i, j)=0, to show that there is no wasted space in the last line of the paragraph. Describe an efficient algorithm for solving the word wrapping problem, so as to minimize the total cost of all the lines used to display the paragraph formed by the words W₁,...,W_n. What is the running time of your algorithm?

Transcribed Image Text:

3 C(i, j) M – (j – i) –ELk k=i