Acknowledgements and Credits
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. 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 Steph 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 have helped to refine
the course materials in numerous ways. 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 fall of 1997, bringing them to essentially the
state reflected in this packet.
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. The lecture on the ``sublist sum''
problem is from Bentley's Programming Pearls, and the lecture on
optimizing the heuristic to solve the traveling salesman problem
is from Bentley's Writing Efficient Programs.
Robert Sedgewick
January, 1998