$4.$ Text Formatting

Background. In typesetting systems, like the LaTeX system in which this problem set is formatted, the input for

paragraphs is given in blocks of plain text consisting of words and punctuation separated by blanks and new lines.

Formatted paragraphs are produced by laying out this text using fixed maximum width L per line by figuring out

where to break each line of text and continue the paragraph on the next line. An innovation of the TeX system on

which LaTeX is based was to phrase paragraph formatting as an optimization problem, which produced superior

paragraph formatting and has been adopted by many other word processing systems.

We will consider a simplified version of this optimization problem in which words are considered indivisible units of

fixed width $($i$.$e$.,$ words cannot be hyphenated and broken up across multiple lines$)$ and punctuation is considered

part of the word it is next to$.$ We will ignore blank space between words.

In our version, the input consists of a sequence of n positive real numbers w$1,...,$ wn representing the lengths that

the words would occupy in a given font in order, together with a positive real number L representing the allowed

width of each line. $($You can assume that each wi $$ L$.)$ It is required that no line be longer than L$,$ so if a line

consists of words t through u then

wt $+$ wt$+1+...+$ wu $$ L

The slack of this line is the difference between the left and right sides of this inequality; in other words, the amount

of extra space left on that line.

We consider an optimal formatting for this input to be one that minimizes the sum of the squares of the slacks

of all but the last line since $($as is usual in paragraph formatting$)$ the last line is simply left$-$justified and we don$$t

care how long it is compared to the other lines.

Example. Consider the sentence:

The quick brown fox jumps over the lazy dog.

You are given as input the lengths of words $1-9,[3,5,5,3,5,4,3,4,4]($note that $$dog$.$ is considered one word of

length $4)$ and a line length L $=12.$ The optimal formatting would have a minimal sum of the squares of the slacks

of $32($breaking lines up as $$the quick$,$brown fox$,$jumps over the$,$lazy dog.$$ with slacks of $4,4,0,$ and $4$

respectively. Note that the slack of the last line is not included.$)$ You only need to determine the minimal sum of the

squares of the slacks, not the formatting of the input words which produces this optimal value.

Problem. Give an efficient dynamic programming solution that finds the minimal sum of the squares of the slacks

from the inputs w$1,...,$ wn$,$ L$.$ You do not need to give the formatting itself $($i$.$e$.,$ which words go on which lines$),$

just the sum of the squares of the slacks for an optimal formatting.

$($a$)$ Clearly state in English what your recurrence$($s$)$ calculate. Be sure to mention any parameters you use.

$($b$)$ Write a recurrence $($or multiple recurrences$)$ that you will use to solve this problem.

$($c$)$ Give a brief explanation of your recurrence; we$$re not looking for a formal proof, but a brief explanation of

what each of the cases represent, and why that set of cases is exhaustive.

$($d$)$ Describe a memoization structure $($or structures$)$ for your recurrence$($s$).$

$($e$)$ Describe a filling$-$order for your memoization structure$($s$).$ I.e$.,$ if you were to write pseudocode for a dynamic

program to solve this problem, what order would you fill in your memoization structure$($s$)?$

$($f$)$ What is your final answer going to be$?($where in the memoization structure should we look?$)$

Hint: You should try to compute possible slacks before trying to find the minimal sum of the squares of the slacks.

The recurrence for RNA Secondary Structure from class is a good model for this problem.