Laboratory Exercise

Intermediate Recursion with Line Drawings

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)

Purpose

Prerequisites

Background

This lab involves designing and coding two recursive algorithms, proving them correct, and deriving mathematical expressions for the amount of work they do. These algorithms both use a class that represents line drawings.

Recursion and Its Analysis

Chapter 6 of Algorithms and Data Structures: The Science of Computing introduces recursion. This laboratory concentrates on aspects of recursion discussed in Section 6.5, and on variations on ideas from earlier sections of the chapter.

Chapter 7 of Algorithms and Data Structures: The Science of Computing discusses induction and recurrence relations, the techniques used to prove recursive algorithms correct and to derive theoretical operation counts for them.

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

Exercise

Design and code recursive methods that solve the problems described below. For each method, also write a proof that the underlying algorithm correctly solves its problem, and write a mathematical derivation of the number of primitive LineDrawing messages (i.e., messages defined in the LineDrawing class, and described in its documentation) that the algorithm sends

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.

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.

Trees

For example, here, from left to right, are line-drawing trees of complexities 1, 2, and 3:

Design and code a recursive algorithm that takes an integer, n, as its parameter and that draws a line-drawing tree of complexity n. Code this algorithm as a method of a subclass of LineDrawing.

Assume as preconditions that n >= 1, that the pen is positioned at the base of the tree’s trunk, and that the pen is heading in the direction the trunk should grow.

Final Details

The Line Drawing Class

LineDrawing.java can be downloaded from the Web at http://cs.geneseo.edu/~baldwin/sc/classes/LineDrawing.java. It is also available in our folder on the “Course Materials” server.

Documentation on the LineDrawing class is also available on the Web, at http://cs.geneseo.edu/~baldwin/sc/doc/. 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 exercise is due at the beginning of your lab session on Monday, March 15. Beware that this the day after break, so you may not be able to get much help on the lab during the week leading up to the due date — do the lab during the March 1 lab session, or during the days immediately thereafter!

Turn in a printout of the code you write for this lab, along with printed copies of the correctness proofs and derivations of numbers of messages. These proofs and derivations can simply be comments in your Java file(s), or they can be on a separate sheet of paper.