| COMP4141 |
Lectures (2017 edition) |
Theory of Computation |
This year's slides will be placed here in PDF format each week. The schedule below is prospective, based on last year's offering, and may change as we proceed. Last year's slides are available via the menu at the left.
Lectures will follow roughly the same pattern as in 2016, with some to be updated. Please tell me about errors, typos, and sins of omission so I can fix them.
These slides are no substitute for your own notes to be taken during the lectures. Much of what is said during a lecture is not on the slides.
| Week | Topic(s) | Slides/Programs | Reading in [Sipser2013] |
|---|---|---|---|
| 1 | subject introduction Sets, functions, and other preliminaries Formal Languages Finite Automata |
slides 1 slides 2 Notes on induction |
Chapters 0&1 |
| 2 | On Proofs Regular Expressions |
slides 3 slides 4 |
Chapter 1 |
| 3 |
Context-Free Languages PDAs, non-CFLs |
slides 5 slides 6 JFLAP |
Chapter 2 (2.1-2.3) |
| 4 | Chomsky Hierarchy |
slides 7 |
Chapter 3 |
| 5 |
Turing Machines Halting Problem Undecidability |
slides 8 slides 9 slides 10 |
Chapter 4 |
| 6 |
mid-session exam
-- 50 min in Monday class Reducing one problem to another Rice's theorem Time Complexity |
slides 11 |
Chapter 5 Chapter 7.1 |
| 7 |
the classes P and NP P vs NP NP-completeness SAT |
slides 12 |
Chapter 7.2-7.4 |
| 8 |
NP reduction examples Space Complexity PSPACE Savitch's Theorem |
slides 13 slides 14 |
Section 7.5 Section 8.1-8.2 |
| 9 |
Games LogSpace |
slides 18 slides 15 |
Section 8.3-8.5 Section 8.6 (handout: Arora-Barak, Section 4.3) |
| 10 |
Turing Reducibility Alternation |
slides 16 slides 17 |
Section 9.2 Section 10.3 |
| 11 |
Complexity Hierarchy Theorems Probabilistic Algorithms, BPP, RP,IP |
slides (hierarchy) slides 20 |
Section 9.1 Section 10.2 |
| 12 |
Approximation & Optimisation IP = PSPACE |
slides 19 slides 21 |
Section 10.1 Section 10.4 |