Welcome to the course. This page will be used to share files related to the course. As of June 7, solutions have been removed from the website to preserve academic integrity. However, other materials will remain in case it is helpful to students.
Course OutlineAs of March 25, the course marking scheme has been changed due to the cancellation of in-person final exams this semester. Your course mark will be computed based on the maximum of two possible schemes, where
Week 1 (Jan 6-10) Topics: Introduction to the course, finite automata and regular languages Reading: Sipser Chapter 1
Week 2 (Jan 13-17) Topics: Turing machines, Church-Turing thesis, equivalence between different models for Turing machines (multi-tape TMs, nondeterministic TMs, enumerators) Reading: Sipser Chapter 3, Page 1-3 of Turing Machines and Reductions
Turing Machine SimulationWeek 3 (Jan 20-24) Topics: Decidable and undecidable problems: diagonalization arguments to prove undecidability, using reductions to prove undecidability Reading: Sipser Chapter 4.2, 5.1 (skip Reductions via Computational Histories), 5.3, Computability and Noncomputability notes (skip Lemma 1 and Pages 11-13)
Week 4 (Jan 27-31) Topics: Further examples of undecidable problems: Rice's Theorem, Post Correspondence Problem Reading: Sipser Chapter 5 (skip Def 5.6-Theorem 5.13 in Reductions via Computational Histories), Computability and Noncomputability notes (skip Lemma 1 and Pages 11-13)
Week 5 (Feb 3-7) Topics: Further examples of undecidable problems: problems related to context-free grammars, Kolmogorov complexity Reading: Sipser 2.1 (up to Definition 2.7 of ambiguity), Sipser Chapter 6.4 Optional Readings: CFLs and Noncomputability notes, Sipser Chapter 6.2
Our coverage of Kolmogorov complexity in class was slightly different from the material covered in Sipser. We talked aboutWeek 6 (Feb 10-14) Topics: Basics of time complexity theory: defining P, NP, and NP-completeness Reading: Sipser 7.1-7.4 (up to Theorem 7.36). Most of this material should be covered in classes like CSC 373 that most students in this class have already taken, so feel free to skim the sections rather than doing a close reading. The most important sections are "Complexity Relationships among Models" in Section 7.1, Theorem 7.20 in Section 7.3 (equivalence between definitions of NP), and Section 7.4 (definition and properties of NP-Complete problems). Optional Reading: Theorem 9.10 in Sipser 9.1 (Proof of the Time Hierarchy Theorem)
Reading Week (Feb 17-21) Office hours for midterm preparation in BA 2283 on Tuesday, Feb 18 and Thursday, Feb 20 between 2-4pm.
Week 7 (Feb 24-28) Topics: NP-Complete Problems and Reductions (Monday/Friday), Midterm Exam (Wednesday) Reading: Sipser 7.4-7.5
In class we presented a sequence of polynomial-time reductions: SAT -> 3SAT -> CLIQUE -> INDEPENDENT-SET -> VERTEX-COVER and the Cook-Levin theorem establishes that each of these problems is NP-Complete.
Proof of the Cook Levin Theorem Slides Images from the slides taken Karp's Reducibility among Combinatorial Problems", Abtruse Goose, and xkcd.Week 8 (Mar 2-6) Topics: Additional Examples of NP-Complete problems: graph colouring, Hamiltonian path, travelling salesperson problem Reading: Sipser 7.5 (up to Theorem 7.55) Optional Reading: NP-Completeness of Subset Sum (Sipser Theorem 7.56), supplementary notes on NP Completeness and NP-hard search problems by Steve Cook, Sipser 10.1 (Approximation Algorithms)
Here are some notes on the NP-completeness of Hamiltonian path.
Here is also a website from the University of Waterloo about solving the travelling salesperson problem. The best known approximation algorithm for Metric-TSP in terms of its approximation ratio is Christofides algorithm and improving it has been an open problem in the area of approximation algorithms.
Week 9 (Mar 9-13) Topics: Space complexity: Savitch's Theorem, PSPACE and PSPACE-Completeness Reading: Sipser 8.1-8.3 Optional Reading: Sipser 9.1 (proof of the Space Hierarchy Theorem)
Rest of the Term Since in person classes have been cancelled due to the ongoing COVID-19 pandemic, classes will transition to online. See the class Piazza for more details. We will try to finish the following topics: