CSC 365F: Enriched Computational Complexity and Computability
Winter 2007

The Undergrad Announcements (UGA) website contains announcements about things of importance to students, such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines.

Lectures: MW 2 in BA B024

Tutorial: F2 in BA 1240

Tutor: Phuong Nguyen

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

Text: "Introduction to the Theory of Computation", by Michael Sipser. (First or Second Edition.) Mainly chapters 3,4,5, and 7.

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:

• 5 assignments worth 10% each (Due in tutorial: Jan 26, Feb 9, March 9, March 23, April 13) Assignments are due at the {\em beginning} of tutorial, since solutions will be discussed during the tutorial.
• 2 closed-book tests worth 10% each (Feb 16, March 30: 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)

• Problem Set 1 Due January 26 in tutorial

• Problem Set 2 Due February 9 in tutorial

• Problem Set 3 Due March 9 in tutorial

• Problem Set 4 Due March 23 in tutorial
  (Revised March 15 at 3pm)

• CORRECTED Problem Set 5 Due April 13 in tutorial
  

• Test 1 February 16

• Test 2 March 30