CSC 365S: Enriched Computational Complexity and Computability
Winter 2010

CSC365H Announcements

Problem Set 2 is now posted below. (Due Feb 12) (Question 5 slightly edited 6pm Feb 2.)

Lectures: MW 3 in BA 1220

Tutorial: F3 in BA 1220

Tutor: Kaveh Ghasemloo

Instructor: Stephen Cook
email: sacook@cs.toronto.edu
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 4:15-5:00 Or make an appointment, or drop in.
E-MAIL QUESTIONS ARE WELCOME.

Text: "Introduction to the Theory of Computation", by Michael Sipser. (Second Edition.) Chapters 3,4,5, 7,8, and parts of other chapters.

References:
M. Garey and D. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Chapters 1-3 especially relevant.

Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms (Second Edition), MIT Press and McGraw-Hill. Chapter 34 on NP-completeness is the relevant chapter here.

Marking Scheme:

• 4 assignments worth 15% each (Due at beginning of tutorial, except the last assignment due at the beginning of lecture: Jan 29, Feb 12, Mar 12, Mar 31) Assignments are due at the {\em beginning} of tutorial/lecture, since solutions will be discussed during the tutorial/lecture.
• 1 closed-book test worth 10% (Feb 26: In tutorial)
• final exam worth 30%

Supplementary Lecture Notes (.ps files from CSC 364H)

• Turing Machines and Reductions
• Computability and Noncomputability
• NP and NP-Completeness

Problem Sets (.ps files)