Intermediate Recursion with Line Drawings

Purpose

Prerequisites

Background

This lab involves designing, analyzing, and coding a series of recursive algorithms that use a class that represents line drawings.

Line Drawings

This lab uses a class named LineDrawing, that represents drawings made from colored line segments. Each segment is straight, so the drawings nominally contain polygons and other angular figures. However, a number of very short straight segments joined end to end and heading in slightly different directions looks like a smooth curve, so the class can in fact be used to draw curves as well as straight-edged figures.

The line drawing class is formally introduced in Chapter 15 of Algorithms and Data Structures: The Science of Computing. For a summary of its abilities, see the sidebar entitled “A Line Drawing Class” in that chapter. However, the class is simple enough to be usable by anyone who understands basic object oriented programming.

Programs that use the LineDrawing class need to include a file named LineDrawing.java. See the “Final Details” section below for information on where to find this file and documentation for the class.

Any Java source file that refers to the LineDrawing class should “import” it, via the statement

    import geneseo.cs.sc.LineDrawing;

at the beginning of the file.

Exercise

Design recursive algorithms that solve the problems described below. Prove each of your algorithms correct, and derive asymptotic expressions for their execution times. Finally, code each algorithm as a method in a subclass of LineDrawing.

Generally, each problem statement includes a precise description of the problem’s preconditions, and defines postconditions implicitly by describing the figure an algorithm should produce. You may define additional postconditions for a problem if doing so helps you determine what code to write around recursive messages.

Valley

Design and code a recursive method for a subclass of LineDrawing that takes a natural number, n, as its parameter and draws a figure that looks somewhat like a cross-section of a valley with stepped sides. Each side should contain n steps. For example, here is a valley whose sides each have 3 steps:

The bottom of the valley can be the same width as one of the steps. The width and height of the steps can be any value.

Assume as a precondition that n >= 0. Also assume as preconditions that the pen is positioned where the left end of the valley figure should be, and that the pen is initially heading right.

Mountain Ranges

A single “mountain” is a peaked shape like this:

A mountain range is a series of these peaks, increasing in height from the ends into the middle. There is a single highest peak, which is the middle peak of the range. Here are two examples of mountain ranges:

Note that a single mountain is a mountain range that only contains 1 peak.

Design and code a recursive method for a subclass of LineDrawing that draws mountain ranges. The algorithm should take two parameters. The first, n, is the number of peaks from one end of the range to and including the center peak. For example, the left-hand mountain range in the picture above has n = 3, while the right-hand one has n = 2. The second parameter is the length of the sides of the outer (i.e., lowest) peaks in the range.

Assume as preconditions that n >= 1, and that the pen is positioned where the left end of the mountain range should be.

Double Spirals

Define a “double spiral” to be a spiral joined at its inner end to a copy of itself. Here are some examples of double spirals:

The first spiral in these examples is red, and its copy blue. Notice that the blue and red spirals really are copies of each other, in that they could be rotated about the point where they connect in order to lie exactly on top of each other.

Design and code a recursive algorithm that draws a double spiral. Code this algorithm as a method of a subclass of LineDrawing. The algorithm can draw a spiral as a series of straight line segments, each of which heads at a slightly different angle than the previous one, and each of which is slightly shorter than the previous one. The algorithm should take the number of segments in one spiral (n) and the length of the first segment (length) as parameters.

Assume as preconditions that n >= 0, length > 0, and the pen is positioned at the outer end of the first spiral, heading in the direction that spiral’s first segment should head.

The two spirals may have different colors, as in the examples above, but don’t need to. The colors make it easier to tell where one spiral ends and its copy begins, but are not essential to the definition of double spiral.

Final Details

The Line Drawing Class

LineDrawing.java can be downloaded from the Web.

Documentation on the LineDrawing class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

This lab is due on Monday, March 7. Turn in printouts of the methods you wrote, along with their correctness proofs and execution time derivations. The proofs and derivations can appear as comments in the code, or on a separate sheet of paper.

In addition to the code, also turn in a few sentences discussing what you can say about the speeds of the algorithms based on the analyses in this lab. For example, can you expect any algorithms to be faster than others? Why or why not? To what extent (if any) can you reach conclusions about the algorithms’ speeds from their asymptotic execution times? How about from the exact operation counts that (presumably) underlie the asymptotic times? (You needn’t discuss all and only these questions, they are merely examples to help start your thinking.)

Portions copyright © 2004. Charles River Media. All rights reserved.

Revised Feb. 27, 2005