COMP4141 |
Lectures (2016 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 2015, 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 |
Pumping (ctd. from Lecture 4) Context-Free Languages PDAs, non-CFLs |
slides 5 slides 6 JFLAP, example files |
Chapter 2 |
4 | Chomsky Hierarchy |
slides 7 |
Chapter 4.1 |
5 |
TMs Halting Problem Undecidability |
slides 8 slides 9 |
Chapters 3-4 |
6 |
Reducing one problem to another Rice's theorem mid-session test -- 1 hour Time Complexity; the classes P and NP |
slides 10 slides 11 |
Chapter 5, 7.1-7.3 |
7 |
P vs NP NP-completeness SAT |
slides 12 |
Chapter 7 |
8 |
NP-Completeness, ctd Space Complexity Savitch's Theorem |
slides 13 slides 14 |
Section 8.1-8.2 |
9 |
Games LogSpace |
slides 15 slides 18 |
Section 8.3-8.5 Section 8.6 (better: Arora-Barak, Section 4.3) |
10 |
Complexity Hierarchy Theorems |
slides (hierarchy) |
Section 9.1 |
11 |
Turing Reducibility Alternation Approximation & Optimisation |
slides 16 slides 17 slides 19 |
Section 6.3 & 9.2 Section 10.3 Section 10.1 |
12 |
Probabilistic Algorithms, BPP, RP, IP, IP = PSPACE Self |
slides 20 slides 21 slides 22 |
Section 10.2,10.4 Section 6.1 |