Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
This document provides information on the Sieve of Eratosthenes lab exercise beyond what appears in the student directions.
The student directions present two versions of Eratosthenes’s algorithm. Most of our students, at least, seem to understand the algorithm(s) well enough to implement the list-based one just from the description in the student directions. However, some students may benefit from being shown simple examples of either or both versions in action. Instructors can present such examples orally, either at the beginning of a lab session or in a prior lecture.
Some students need help inventing recursive list traversal algorithms. We find that showing these students how to use the structure of a list as a guide to designing the algorithm helps greatly. Specifically, let each part of the definition of “list” correspond to a part of the algorithm: the definition has empty and non-empty cases, the algorithm should have cases to handle each of these kinds of list; the definition identifies two pieces (head and tail) of a non-empty list, the part of the algorithm that handles non-empty lists should have code to deal with each of these pieces; one of the pieces is defined recursively, that piece should be processed recursively in the algorithm. Showing students how to construct an algorithm in such a manner from the definition of the thing on which the algorithm operates both helps students understand how and why the resulting algorithm works, and helps them imagine how they could approach similar algorithm design tasks in the future.
A particularly elegant way to implement the main algorithm for building a
list
of primes is to encapsulate it in a constructor for PrimeList. The
largest number
to consider putting in the list, n, is the only parameter to
this constructor. Such a constructor exposes students to the idea that a subclass
can have constructors that don’t simply parallel those of its superclass,
and reinforces the role of constructors as the algorithms that initialize new
objects. Instructors may wish to require students to implement
the main algorithm in this manner.
The number of primes less than or equal to n is asymptotically n / ln n (see, e.g., Graham, Knuth, and Patashnik, Concrete Mathematics). Students do not need to know this in order to form hypotheses, however. As suggested in the student directions for the lab, the most important role of this experiment is to help students learn to conduct sound experiments and carefully interpret experimental data. Instructors should insist that students reach the conclusion that is consistent with their data, but whether that conclusion is that the initial hypothesis was right or wrong is less important.
n / ln n is not that different in its growth rate from n. Students who hypothesize that the number of primes less than or equal to n is proportional to n may thus not see clear evidence that their hypothesis is wrong, particularly if they do not examine a large range of n values, or if they are not sensitive to small trends in the constants of proportionality that they calculate.
Students may find the experiment easier to do if, in
addition
to
addIfIndivisible, PrimeList handles
a message that returns the number of items in a list. Code for handling this
message appears as the count method in section 11.3.2 of Algorithms
and Data
Structures: The Science of Computing, but is not included in the final List class.
Students who want to use such a message must therefore at least copy the code
from
the
text
into
their
own
program,
and
adapt
it
to
work in a subclass of List. This is a modestly interesting exercise,
but even
more valuable is the experience of writing code because it solves a real problem
that the student faces, not simply because it was demanded by an instructor.
Thus
the student
directions
don’t
tell students that PrimeList should handle count messages,
but we hope
that many students decide for themselves that it should.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin