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