Test data for Problem 16-2.

Boundary cases for M=50:

This_very_long_word_should_fit_onto_a_single_line.

This_paragraph_should_fit_on_one ____________line.

but_this_paragraph_should_require two________lines.

If paragraphs contain only a few words

then it doesn't matter very much

if the computational algorithm employed to separate words into lines

is asymptotically inefficient.

When paragraphs contain hundreds or thousands of
words, however, the asymptotic efficiency of
line-breaking

becomes a matter of no small concern.

For example, the last two paragraphs in this file of test data

are far too large to be formatted

by an algorithm that requires exponential time.

Greedy algorithms are usually efficient but may not be optimal.

The greedy algorithm for breaking words into lines
works well enough to be used in low-end word
processors for personal computers, but it does not
work well enough to be used for
professional-quality typesetting. The problem with
the greedy algorithm is that it tries to cram as
many words as possible onto the current line, and
never even considers the possibility that
shortening the current line might help to make the
next lines look better. The greedy algorithm tends
to produce one or two short lines that stand out
like a sore thumb. When typeset with a line length
of 50, this paragraph is a good example of that.

Instead of attempting to make the current line as
long as possible, a better algorithm tries to
maximize the neatness of the lines, or to minimize
their ugliness, using some mathematical function
that correlates with readers' perceptions of
neatness or ugliness. It turns out that a neat
arrangement is an arrangement in which all lines
have about the same length.  This perception of
neatness can be modelled by a cost function that
sums the squares or cubes of the absolute values
of the variance of a line from its ideal length.