MC28 Lab 3: Formatting Paragraphs (Fall 1996)

Due: October 30, 1996

Pre-lab

In Lab

1. Do exercises 12.15 and 12.16, from pages 433-434.
2. Do exercises 12.17 and 12.18, from pages 434-435.
3. Now, in a deviation from the text, we won't use the format-paragraph procedure on page 436 to do exercise 12.19 on page 437. Instead, we'll use the format-paragraph-2 procedure from pages 438-439. (You can find this in the file /mcs-sever/Public/ConcAbs/chap12.scm. That file also contains the definitions of string-width and space-width, which you'll need.) Evaluate these definitions, and use them together with your own procedures to break into lines of maximum length 15 characters a paragraph consisting of the first 15 words from the list that words is defined as in the file /Net/solen/u8/Faculty/em/max/MC28/words.scm. (To get the first 15 words from the list, or any other number of words, you can use the first-elements-of procedure from page 208, which is in /mcs-server/Public/ConcAbs/chap7.scm.) See how long it takes. 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. 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?
4. Next you will write a memoized version. (You will write the same procedure as you would have wound up with had you done exercise 12.20 to write it a harder way, then exercise 12.21 to convert it to the easy way -- but we're having you write it the easy way in the first place.) Make your own copy of the format-paragraph-2 procedure and change its name. Now, make the changes necessary to memoize it. You will need to change the two places where format-paragraph-non-memo is called to instead call a new format-paragraph-memo procedure. You will also need to add an internal definition of this format-paragraph-memo procedure. It will need to use a table, retrieving the value corresponding to i from that table if it is already in there. If not, it can use the existing format-paragraph-non-memo to compute the value, which it should store into the table before returning it. 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.
5. 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