MCS-177 Project: Fractal Curves

Due: Monday, October 29, at the beginning of class

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

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) 400)

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

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. You can also get some sense of how this project report will be graded by looking at the grading sheet that we use.

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(d, n) 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.