Reference Material

A gentler approach to the matter is presented in the following text (both editions are available in the library; I reserve the right to place them on reserve).

In principle, the textbook will do. However, if you are interested to see other points of view, you could take a look at the following nice compendium of theoretical computer science (which covers much more material than this course):

Mikhail J. Atallah, Algorithms and Theory of Computation Handbook, CRC Press, 1999. Call number QA 76.9.A43 A43 1999.

For later in the term, the following may become useful:

Michael R. Garey and David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, Freeman, 1991. Call number QA 76.6 .G35 1991.

A paper in the Communications of the ACM looks at how people have tried to solve the P=NP problem, at how this problem has shaped research in Computer Science, and what are the prospects of actually solving the problem.

Here is a collection of links related to theoretical computer science.