Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
These notes discuss the “Intermediate Recursion with Line Drawings” laboratory exercise. This exercise develops students’ abilities to design algorithms that use the patterns of recursion discussed in section 6.5 of Algorithms and Data Structures: The Science of Computing (and even, in fact, a pattern not discussed in chapter 6 at all).
This exercise deliberately asks students to solve more problems than would be reasonable in a single 2 or 3 hour lab session. We expect instructors to pick and choose a subset of the problems to do in any single lab session. This allows instructors to vary the exact problems they do from one offering of a course to the next (reducing opportunities for students to “recycle” old solutions), or to do several lab sessions based on this one exercise.
The problems in this exercise can also be mixed with problems from the exercises on Elementary or Intermediate recursion with robots, providing further variety in the number or nature of laboratory exercises available for a course. This is particularly convenient for instructors who want to expose students to a large variety of applications of recursion.
While the exercise as written only asks students to design and code algorithms,
it is easy to extend the exercise to ask students to prove their algorithms
correct and/or to derive performance formulas for them (e.g., to derive expressions
for the number of LineDrawing messages each algorithm sends).
Such extensions are particularly appropriate if this lab is used after covering
induction and/or recurrence relations (Chapter 7 of Algorithms
and Data Structures: The Science of Computing). In general, it is a
good idea to begin asking students to do mathematical analyses of their algorithms
as soon as possible, so that students do not fall into the belief that algorithm
design and coding are the most important activities in computer science, and
analysis only an afterthought.
Most of the problems in this exercise have features or idiosyncrasies that instructors may need to be aware of. In particular, many algorithms in this exercise involve values that determine, e.g., the sizes of features in a drawing. Students can choose these values largely as they wish, although we offer some suggestions below. We encourage students to define these values as named constants (“final” variables in Java).
Students may wonder whether they should design many of the algorithms in this exercise around recursions that “work in” from the sides of a figure, or that “work out” from the center. Working in generally leads to simpler algorithms. If students seem stuck on the idea of working out from the center of a figure, instructors can suggest that there is another way of thinking about the algorithm before telling students outright to work in.
When designing any recursive algorithm, we try to get students to start with a recursive definition of the problem they need to solve. A high-level algorithm for solving the problem can often be transcribed directly from such a definition. Thus, for example, if we find a student struggling to design an algorithm for drawing a valley, we will start helping that student by asking them to describe what a valley looks like in terms of a smaller valley (two steps, with the smaller valley in between them). Similarly, one can ask students to describe the results they want from any algorithm in this lab in terms of a smaller set of similar results (e.g., a mountain range consists of two peaks with a shorter mountain range between them, etc.)
The valley method needs one or more constants for the height and width of each step in a valley, as well as for the width of the valley floor. We used the same constant, with a value of 20, for all of these, although there is no reason why they need to be the same.
The length of the sides of mountains needs to increase as the mountain range method sends recursive messages. The simplest way to increase this length is to add a small increment to the previous length — we used an increment of 10 pixels. An interesting alternative is to multiply the previous length by a small factor. Values around 1.5 work well.
Mountain ranges have a second constant that programmers must choose: the angle at which the lines in a peak ascend or descend. The pictures in the student directions use an angle of 60 degrees.
For many students, past experience will suggest a base case of 0 for the recursion in this algorithm. However, because the problem specifies that a mountain range has a unique central peak, 1 is a better base case.
Our algorithm for this problem used a helper method to draw a peak. The main mountain range method calls this helper in several places. Such use of helper methods is a good program design technique to point out to students in connection with this problem. Because the helper exists only to support a particular mountain range algorithm, it should be private. This is a good opportunity to discuss the difference between public and private methods, and the reasons why a programmer would use each.
As suggested in the student directions, the way to draw a curve is to draw a number of short, straight, line segments, each heading in a slightly different direction from the previous one. In our experience, students understand this idea fairly readily, although some may need help with it. One way to approach it if students do need help is to point out how polygons become more circular as they have more sides. Instructors can actually ask students to draw a series of polygons with increasingly many sides as a warm-up exercise if desired.
The length of each straight segment, and the amount by which the pen’s heading changes between segments, are both constants for which students can choose values. Segment lengths of about 5 pixels, and changes in heading of about 5 degrees, work well.
Like mirrored curves, a spiral can be drawn as a series of short straight segments, each heading at slightly different angle than the previous one. See the discussion of Mirrored Curves for a way of explaining this idea to students, although that is seldom necessary, in our experience. In order to get a spiral rather than a circle, either the segments should get shorter, or the change in angle greater, as the spiral winds inward. We have specified the double spiral problem in such a way that changing segment length will be the most natural thing to do.
For many students, the natural way to shorten segment length is to subtract
a small amount. However, this can lead to negative lengths as a spiral
winds inward. When lengths become negative, the movePen method
in class LineDrawing will move the virtual pen backwards (i.e.,
180 degrees from the direction in which it is supposedly heading). If students
produce figures that abruptly
reverse direction, this may be what is happening.
The best way to reduce segment length without it ever becoming negative is to multiply it by a fraction slightly less than 1. We generated the double spirals in the student directions by making each segment 0.99 times as long as the segment outside it in the spiral. Note that because this multiplication decreases segment length exponentially, a surprisingly large fraction is necessary if spirals are to have very many segments (and spirals that wind much may have 100 or more segments).
In addition to a factor by which to decrease segment length, students will need to choose a value by which to change the pen’s heading in their double spiral algorithms. We found 4 degrees to work well.
Drawing trees is the only problem in this lab where an algorithm needs more than one recursive message in a single arm of its main conditional. Chapter 6 of Algorithms and Data Structures: The Science of Computing provides no examples of such recursion, but students who have had experience with other patterns of recursion are generally able to understand and use this one. Pointing out the definition of “line-drawing tree” in the student directions, and how it uses recursion twice in a single arm, can help students discover this pattern, if help is needed.
Chapter 15 does discuss recursive tree-drawing algorithms, although the ones in that chapter are more sophisticated than necessary for this lab. Nonetheless, some students discover those algorithms, and adapt them to this lab. There is little that instructors can do to completely prevent this, so instructors who insist on students designing all their algorithms from scratch may want to exclude “line-drawing trees” from their lab exercises.
Many students don’t realize at first that they have to move the pen
back to the place where a tree forks after they draw the first of its recursive
subtrees. This oversight leads to drawings that look, at best, like a series
of half-trees joined trunk to twig in a jagged pattern. Once students recognize
the need to return the pen to the fork, there are two ways to do so: either
write code with a postcondition
that
drawing
a tree
leaves
the pen
at the
base of that
tree’s trunk, or use the getPositionX and getPositionY messages
to find out the pen’s position before drawing the first subtree, and setPosition to
return the pen to that position afterwards.
This is the only problem in this exercise that does not involve line drawings. As such, instructors can use it to add variety to a laboratory session.
The problem is fairly easy to solve recursively, probably easier for most students than the other problems in this exercise. It requires a little bit of thought to handle both even and odd parameters, which may lead to an algorithm with two recursive cases (one for even numbers and one for odd numbers), or it may lead to an algorithm that subtracts one from an even parameter before reaching the core recursive part of the algorithm (so that the core only needs to handle odd numbers).
The natural recursion for this problem decreases its parameter by 2 (or, in some solutions, by 3 if the parameter is even). This may be the first time some students have seen a recursion in which the parameter decreases by an amount other than 1.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin