SUNY Geneseo, Department of Computer Science

Lab 7

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Friday, October 17

Purpose

Background

This lab asks you to design algorithms for a class that represents simple line drawings. The lab also requires you to set up and solve some recurrence relations.

Line Drawings

In this lab you will use a pre-existing Java class that represents line drawings -- i.e., windows that contain drawings made up of lines. This class is named LineDrawing. The general strategy for drawing a picture with this class is to create an instance of the class, then send that instance a series of messages that describe how to draw the picture. The result will be a window on the screen containing the picture you described. The overall metaphor for describing how to draw pictures with LineDrawing objects is that there is an invisible pen that can move over the picture leaving a line as it moves; messages to LineDrawing objects tell them to move their pen forward a certain distance, change the direction in which the pen moves, etc. Full Documentation on LineDrawing is available on the World Wide Web, at http://cs.geneseo.edu/~baldwin/sc/doc/; click on the "LineDrawing" entry in the left panel. You will almost certainly need this documentation while doing this lab.

You can get a copy of the LineDrawing class from our course folder on the "Course Materials" file server, or Download It from the Web at http://www.cs.geneseo.edu/~baldwin/sc/LineDrawing.java. Add the LineDrawing.java file to projects just as you added Robot.java or RobotRoom.java to previous projects.

Note that the LineDrawing class is defined in the geneseo.cs.sc package. Thus you can either refer to class LineDrawing by its full name, geneseo.cs.sc.LineDrawing, or import it with the statement

    import geneseo.cs.sc.LineDrawing;

in any files that directly refer to it.

Recurrence Relations

See Section 7.2 of The Science of Computing for information on recurrence relations. In particular, Section 7.2.1 introduces the mathematics of recurrence relations, and Section 7.2.2 presents examples of their use in analyzing algorithms.

Exercise

The lab exercises consist of a warm-up exercise on recurrence relations, a pair of algorithms to design and code as part of a subclass of LineDrawing, and finally an analysis of the number of LineDrawing messages that one of your algorithms sends.

Warm-Up

Find, and prove correct, closed forms for the recurrence relations

• f(n) = 5 if n = 0
• f(n) = 2 + f(n-1) if n > 0

and

• g(n) = 1 if n = 0
• g(n) = 3g(n-1) if n > 0

Spiral

Design and code a recursive algorithm that makes a LineDrawing object draw a spiral, such as the following:

You can draw curves as a series of short, straight, line segments. This is a good strategy to use for drawing spirals. I suggest that you give your spiral algorithm two parameters, one that says how many segments to put in the spiral, and another that says how long to make the first segment. The parameters to recursive messages can then specify fewer segments, and a slightly shorter first one. For example, the spiral above consists of 100 segments, starting with one 10 units long.

I suggest that you make your spiral algorithm a method of a subclass of LineDrawing.

Mirrored Spirals

Define a "mirrored spiral" to be a spiral joined at its inner end to its own mirror image, for example:

Here, the first spiral is red, and its mirror image blue. The above spirals don't wind very much, but as the spirals wind more the mirroring becomes more complicated. For example:

Design and code a recursive algorithm that draws a mirrored spiral. The algorithm should take the number of segments in one half of the image and the length of the first segment as parameters, much as the simple spiral algorithm above does.

Once again, I suggest coding your mirrored spiral algorithm as a method of a subclass of LineDrawing.

Finally...

Use recurrence relations to derive the number of primitive LineDrawing messages (i.e., movePen, setAngle, getAngle, setColor, getColor, etc.) that either of the above algorithms sends, as a function of the algorithm's "number-of-segments" parameter. For up to 2 points extra credit, derive the number of primitive LineDrawing messages for both algorithms.

Follow-Up