MCS-177 Project: Fractal Curves

Due: April 4, 2001

Problem

In this project, you will experiment with tree recursion by looking at fractal curves. Complete the project and its report individually (not in partners).

Project Report

As usual, write up a lab report that explains the project to an audience generally knowledgeable about Scheme, but ignorant of specifically what you did. Answer all of the questions posed, but do not simply write up your lab as a sequence of exercises. Instead, try to convey the big picture of what the project accomplished. Remember, there are some tips in the document entitled Suggestions for clear reports in computer science courses.

Some notes on Exercise 4.7 are in order. We do expect you to be able to prove that the length of the C-curve is determined by the pattern. One way to do this is to determine a formula L(dn) for the length of a level-n C-curve between two points distance d apart. You can then use induction on n to prove that the formula is correct for all d and for all nonnegative integers n. If you do the proof this way, you will be proving a theorem with two variables in it, d and n. Note that when you write the induction hypothesis, you should rename both variables, but only add a restriction to the one corresponding with n. For an example of this, see page 55. The theorem on that page involves the two variables a and b. The induction hypothesis renames them to i and k, and adds the restriction k < b.

Computer Exercises

Work through all the exercises of section 4.3 in the text, except that exercise 4.8 is an optional problem you may do if you have time and interest.

One technical tip: if you can't see a fractal with fine details clearly because it is too small, you can enlarge the image in Scheme by using the resize-image procedure, which is built-in to our Scheme. For example,

  (resize-image (line 0 0 1 1) 500)
would give you an image of a line from the center of the image to the upper-right corner, but it would be much larger than usual.

Rather than typing in the definition of c-curve, you can click on the following file in Netscape and save it somewhere in your home directory.

  ~mc27/labs/fractal-curves/c-curve.scm