MC28 Lab 3: Formatting Paragraphs
(Spring 1997)
Due: April 7, 1997
Pre-lab
In this lab, you will be applying the technique of memoization to the
particular problem of breaking a paragraph into lines. Since this is
covered in section 12.5 of the textbook, you should read that section.
Important reminders
Be sure to test your procedures individually as you go, rather than
only testing them as they are used by the ultimate paragraph
formatting procedure.
Also, please remember that the code from the book is available online,
in the /mcs-server/Public/ConcAbs
directory, so that you
don't need to type in the definitions that are in the book.
In Lab
-
Do exercises 12.17 and 12.18, from page 458.
-
Do exercises 12.19 and 12.20, from page 459.
-
Do exercise 12.21, from page 460.
-
Do exercise 12.22 from page 461. As a source of test data, the file
/Net/solen/u8/Faculty/em/max/MC28/words.scm
contains a
definition of words
as a list of words (i.e., a list of
strings). Start by trying to use the first 15 words from that list,
breaking them into lines of maximum length 15 characters. To get the
first 15 words (or any number) from the words
list, you
can use the first-elements-of
procedure from chapter 7,
which is in /mcs-server/Public/ConcAbs/chap7.scm
. See
how long it takes to break these first 15 words into lines. You
can view the result of the line-breaking more visually by applying the
procedure display-lines
to the result; this procedure is
defined in the words.scm
file. It takes a list of list
of strings, one per line, such as make-lines
should be
producing.
Now try scaling the maximum line length up from 15, and
(independently) try scaling up the number of words beyond 15. How
rapidly does the time increase?
-
Do exercise 12.23 on page 462. Make sure that your new procedure
produces the same results as the old one. Now compare its performance
with that of the non-memoized version, again increasing both the
maximum line length and number of words. In addition to comparing
performance in the same range of problem sizes, see how the memoized
version performs on problem sizes that were too big to test with the
non-memoized version.
-
If you want to do more careful quantitative performance measurements,
you might want to use the timing procedure in the file
/Net/solen/u8/Faculty/em/max/MC27/time.scm
; this is the one you
used in the MC27 lab concerning perfect numbers. You could also make
your own variation on the timing procedure if you wanted somewhat
different features.
Postlab
As usual, write up a lab report that explains all of
what you did to an audience generally knowledgeable about Scheme. If
you have quantitative performance data, it would be good to present it
graphically (by, for instance, plotting running time as a function of
number of words) to make it easy to interpret. Be sure not only to
address the programming aspect of your work, but also the asymptotic
performance comparison you did between the versions with and without
memoization.
Course web site: http://www.gac.edu/~max/courses/S97/MC28/
Instructor: Max Hailperin <max@gac.edu>
Other lab instructor: Karl Knight <karl@gac.edu>