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

  1. Do exercises 12.17 and 12.18, from page 458.

  2. Do exercises 12.19 and 12.20, from page 459.

  3. Do exercise 12.21, from page 460.

  4. 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?

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

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