4:00 — 4:50pm Monday/Wednesday/Friday in EN-2043. No class on Thanksgiving week.
Office hours during lecture weeks:
Office hours after lecture weeks: * Mondays, Wednesdays, Fridays from 4:00 pm in EN-1058. Please email to make sure I will be there.
2022-09-07: Practicalities. Course plan. Examples of problems. Decision and search problems. Notes.
2022-09-09: Deterministic Finite Automata. Nondeterministic Finite Automata. Notes. See also Sip12 Sections 1.1 (Formal definition of a finite automaton, Examples of finite automata, Formal definition of computation) and 1.2 (Formal definition of a nondeterministic finite automaton).
2022-09-12: Equivalence of Deterministic and Nondeterministic Finite Automata. Notes. See also Sip12 Section 1.2 (Equivalence of NFAs and DFAs).
2022-09-14: Size separation between Deterministic and Nondeterministic Finite Automata. Regular operations. Notes. See also Sip12 Section 1.3.
2022-09-16: Regular expressions and languages. Non-regular languages. Pumping lemma and applications. Notes. See also Sip12 Section 1.4.
2022-09-21: Proof of pumping lemma. Pushdown automata. Notes. See also Sip12 Section 1.4 and 2.2.
2022-09-23: Context-Free Grammars. Notes. See also Sip12 Section 2.1.
2022-09-26: Ambiguity. Pumping Lemma for CFLs. Turing Machines. Notes. See also Sip12 Sections 2.1. (Ambiguity), 2.3, and 3.1.
2022-09-28: Formal Turing Machines. Variants of Turing Machines. Notes. See also Sip12 Sections 3.1 and 3.2.
2022-10-03: Multi-tape Turing Machines. Nondeterministic Turing Machines. Church—Turing thesis. Notes. See also Sip12 Section 3.2.
2022-10-05: Undecidability. Diagonalization. Universal language. Undecidability of universal language. Recognizable and co-recognizable languages. Notes. See also Sip12 Section 4.2.
2022-10-07: Reductions. Mapping reductions. Notes. See also Sip12 Sections 5.1 and 5.3.
2022-10-17: Mapping reductions. Oracles. Turing reductions. Notes. See also Sip12 Sections 5.3 and 6.3.
2022-10-19: Review.
2022-10-24: Arithmetic hierarchy. Notes.
2022-10-26: Arithmetic hierarchy. Notes.
2022-10-28: Kolmogorov complexity. Randomness. Notes. See also Sip12 Section 6.4.
2022-10-31: Introduction to Gödel’s incompleteness theorem. Self-reference. Notes. See also Sip12 Section 6.1.
2022-11-02: Recursion theorem. High-level proof of Gödel’s incompleteness theorem. Notes. See also Sip12 Sections 6.1 and 6.2.
2022-11-04: First-order theories, proof systems, lemmas towards Gödel’s incompleteness theorem. Notes. See also Sip12 Section 6.2.
2022-11-08: Time complexity. Notes. See also Sip12 Section 7.1.
2022-11-09: Polynomial time, classes P and NP. Notes. See also Sip12 Sections 7.2 and 7.3.
2022-11-10: NP in EXP, polynomial time reductions, SAT, 3-SAT and Clique. Notes. See also Sip12 Sections 7.1 and 7.4.
2022-11-14: Clique. NP-hardness and completeness. Notes. See also Sip12 Sections 7.3 and 7.4.
2022-11-16: Review. Notes.
2022-11-23: Computability and complexity. Notes.
2022-11-25: Polynomial hierarchy. Oracles. Notes.
2022-11-28: MaxSAT. Cook—Levin theorem. Notes. See also Sip12 Section 7.4.
2022-11-30: Space and depth complexity. Circuits. Notes. See also Sip12 Sections 8.0, 8.2, 9.3.
2022-12-02: Review.
Auto-graded multi-attempt drills on D2L: 15% total. For each drill, your grade will be an average of all your attempts for that drill.
2 tests of 25% each. Dates TBD (likely mid-October and mid-November). There will be practice problem sets posted with problems similar to what will appear on the tests, and you are welcome to submit your solutions for feedback.
A final exam of 35%. You have to pass the final exam to pass the course.
An optional project. If you decide to do it, your project will be 15% of the total grade and final exam only 20% (you still need to pass the final).
Additionally, a bonus “bug bounty” for finding errors in lecture notes, drills, problem sets, and tests. If you find a bug, please post it on the respective discussion board on D2L; the first person to post each bug gets the bonus. You can post multiple bugs and get the bonus more than once.
The main reference is the book:
Complementary books include:
Computational Complexity: A Modern Approach. Arora, Barak.
Computational Complexity. Papadimitriou.
Many similar courses have useful lecture notes publicly available on the web. In particular, see the notes for a past similar course at MUN.