CSC 365S: Enriched Computational Complexity and Computability
Winter 2010

CSC365H Announcements

Unofficial Final Marks are now available. Send me an email request.

Click here for this year's final exam.

If you like CSC 365, consider taking the graduate version CSC 2401H next year. It's not much harder, and it's open to undergrads with permission.

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)