Theory of Computation
CSC 389 and CSC 544


Technical Books

Hopcroft, Motwani, Ullman is an updated version of the classical Hopcroft, Ullman text on automata theory. Presentation is much improved. Odifreddi's book covers computability theory (decidability) emphasizing the philosophical and scientific context. Cooper is a shorter introduction, that, however, often goes into surprising depth. Garey, Johnson is the standard guide to NP-completeness theory.

Background and History

Fiction and popular accounts


Marcus Schaefer
Last updated: December 9th, 2003.