Philippe Giabbanelli has typed his lecture notes in French (for the Winter 2007 incarnation of the course) and has consented to make them available to the world.
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 recent 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. Note that you need to be on Bishop's campus or have an ACM account in good standing to read the paper.
Here is a collection of links related to theoretical computer science.