Acknowledgements and Credits
Robert Sedgewick
January, 1999
These course materials are mostly original, but some things are based
on sources in the literature or are the work of others. This course is far
from a finished product, so detailed attribution is hardly
appropriate, but the following sources of help are reflected in the
printed material given here and must be acknowledged. I apologize for
any inadvertant omissions.
I developed most of the material in this course in 1992-4 and
revisited and revised in 1997-8. Many people provided feedback on the
material as it was being developed, most importantly Anne Rogers, Dave
Hanson, and Michael Cohen, who co-taught the course, kept in touch
with what the students were doing, and Stef Damianakis, who worked
with us on the precepts and did a lot of the real teaching in the
first offering of the course. Alex Gounares, Jon Mcallister, and Gun
Sirer pretested several of the programming assignments and provided
valuable input.
A. Appel, S. Arora, B. Chazelle, D. Hanson, A. LaPaugh, and A. Yao
taught the course in 1994-7, and several of them helped to refine the
course materials. In particular, Hanson led the charge to bring the
course fully online, and R. Shillner further developed the online
materials in 1997. I edited and updated all of the materials in the
1997 and 1998, bringing them to essentially the state reflected here.
Kevin Wayne and Lisa Worthington provided valuable feedback, particularly
for the exercises.
Programming Assignments
The basic calculation from Program 2 is from Dewdney's Turing
Omnibus; its potential as an ``easy'' assigment was brought to my
attention by Mike Weiksner. Program 3 is adapted from an assignment
originally developed by S. Arora and A. LaPaugh. Program 6 was
conceived and developed by Gun Sirer. Program 8 was developed by Gun
Sirer and Jon Mcallister; I updated it to Java in 1997.
Lectures
Sources for the logical design lectures include the old book
The Man-Made World by David, et. al., Principles of Computer
Science by Schaffer, and Dewdney, though not much of the material is
directly adapted from any of these sources. The dragon curve lecture
originated with Knuth, dating back at least to the early 70s. Sources
for the theory of computation material include Dewdney, Schaffer, and
Harel's Algorithmics. The Turing machine setup is from Harel,
and the Halting problem approach is from Aho and Ullman's
Foundations of Computer Science.