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 inadvertent 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'' assignment 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.


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.