CSC 365S: Enriched Computational Complexity and Computability
Winter 2009

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.

CSC365H Announcements

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:

• 5 assignments worth 10% each (Due at beginning of tutorial, except the last assignment due at the beginning of lecture: Jan 23, Feb 6, Mar 6, Mar 20, April 8) Assignments are due at the {\em beginning} of tutorial/lecture, since solutions will be discussed during the tutorial/lecture.
• 2 closed-book tests worth 10% each (Feb 13 , March 27 : 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 23

• Problem Set 2 Due February 6

• Problem Set 3 Due March 6

• Problem Set 4 Due March 20

• Problem Set 5 Due Wednesay, April 8

• Test 1 Feb 13

• Test 2 March 27