Announcements
Marker's Comments and Solutions to PS4 posted below.
Lectures: M 3-4 in BA 2175 and F 3-4 in BA2179
Tutorials: W 3-4 in BA 2175
Tutor: Dustin Wehr
Instructor:
Stephen Cook
,
email: sacook@cs,
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: Monday 4:15 - 5:00, Wednesday 4:30 - 5:30
Or make an appointment, or drop in.
QUESTIONS VIA EMAIL ARE WELCOME.
Text: "Computational Complexity" by Sanjeev Arora and Boaz Barak
The course will cover roughly Chapters 1 - 7, and parts of
Chapters 14, 17 and possibly other topics.
Click here for Allan Borodin's Lecture Note on computational complexity. Lectures 17 - 20 on Boolean circuit complexity and Alternating Turing Machines are especially relevant.
Click here for old lecture notes on "Turing Machines and Reductions". Of special interest for this course are pages 8-10 describing search problems and polynomial time Turing reductions (i.e. `Cook reductions').
References:
Michael Sipser: Introduction to the Theory of Computation
[More Elementary -- Chapter 7 is a good source for NP-completeness]
Christos Papadimitriou: Computational Complexity
Ding-Zhu Du and Ker-I Ko: Theory of Computational Complexity
Michael Garey and David Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. [A classic reference giving hundreds of NP-complete problems.]
Marking Scheme: Marks will be based on four problem sets.
Problem Sets (.ps files)
Click here for last year's web site for CSC 2401, including problem sets.