CSC 463H: Computational Complexity and Computability
Marks for Problem Sets 1-3 and the Midterm Exam are accessible on the course's Quercus page.
Schedule for the week of April 1-5:
Monday: Tutorial (2-3pm in the usual classroom) going over solutions to Problem Set 4. Office hours take place 3-4pm in BA6214.
Wednesday: Final regular lecture.
Friday: Optional review and question-and-answer session (2-3pm in the usual classroom).
There will be office hours on Monday April 8, 3-4pm in BA6214
The Final Exam takes place Wednesday April 10, 7-10pm in EM 119 (Emmanuel College).
The exam covers both computability and complexity (Chapters 4,5,7,8 of the textbook).
In weeks 10-12, we will cover Chapter 8 on Space Complexity (and parts of Chapter 9, time permitting).
Wrap up NP-completeness; discussion of Search and Optimization Problems (read supplementary lecture notes, link below)
Sipser Chapter 7.4-7.5 and supplementary lecture notes on "NP and NP-completeness" (link below)
Sipser Chapter 7.1-7.3 (Time Complexity)
Sipser Chapter 6.4 (Kolmogorov Complexity)
ASSIGNMENTS (due at the start of lecture or tutorial)
Problem Set 1 due Friday January 25
Problem Set 2 due Friday February 15
Problem Set 3 due Friday March 15
Problem Set 4 due Monday April 1
In Question 3, you may use the fact that NL = coNL and show that 2SAT is coNL-complete by giving a reduction PATH ≤L 2SAT.
Lectures: MW 2-3 in Bahen 1200
Tutorial: F 2-3 in Bahen 1200
Benjamin Rossman (email@example.com)
Office hours: M 3-4 in Bahen 6214
Adrian She (firstname.lastname@example.org) and
Evi Micha (email@example.com)
Click here for the course information sheet.
Text: "Introduction to the Theory of Computation"
by Michael Sipser (Second or Third Edition). Chapters 3,4,5,7,8, and
part of Chapter 9.
- 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.
- Computability Theory (5 weeks): Turing machines, Church's Thesis,
decidability and semi-decidability, diagonal arguments,
the Halting Problem and other undecidable problems, reductions,
- Computational Complexity (7 weeks):
The classes P and NP,
polynomial time reducibility, NP-completeness, Cook-Levin Theorem,
various NP-complete problems, intractable problems, log space,
- 4 assignments worth 10% each (first two assignments due Jan 25 and Feb 15).
Assignments are due at the beginning of tutorial/class,
since solutions will be discussed during the tutorial/class.
- 1 closed-book test worth 20% (March 1 in tutorial)
- Final exam worth 40%
The work you submit must be your own.
You may discuss problems with each other; however,
you should prepare written solutions alone.
Copying assignments is a serious academic offence and will be dealt with
Supplementary Lecture Notes (.pdf files from earlier versions of this course)
Previous Years' Problem Sets (.pdf files)
Previous Years' Midterm Tests