-
Overview
[HU]: 1-2, 8-10; [Sip]: 1-3
-
Models of computation
-
DFA, NFA
[HU]: 13-21, 24-25; [Sip]: 35-44, 47-54
-
PDA
[HU]: 107-112; [Sip]: 114-116
-
DTM, NTM
[Sip]: 165-175, 185-187; [more]
-
Grammars
[HU]: 77-87, 220-221
-
Regular expressions
[HU]: 28-29
-
The Church-Turing thesis
-
Partial recursive functions
[note] --- not covered this time
-
Turing machine variants
[HU]: 159-165
-
RAM model of computation
[HU]: 166-167
-
Unrestricted grammars
[HU]: 221-223
-
Regular languages
-
Regular expressions vs automata
[HU]: 30-35
-
Equivalence of NFAs and DFAs
[HU]: 22-27
-
Pumping lemma
[HU]: 55-56, 63-64; [Sip]: 80-82
-
Closure properties
[HU]: 58-60
-
More closure properties
[HU]: 60-63 --- AR
-
Context-free languages
-
Equivalence of CFGs and PDAs
[Sip]: 117-124
-
CFG in CNF
[Sip]: 108-111, 157 exer 2.26
-
Pumping lemma
[Sip]: 125-129
-
Closure properties
[HU]: 131, 134-136
-
More closure properties
[HU]: 131-134 --- AR
-
Universal Turing machines
[HU]: 181-182, 183-184
-
Decidability
-
Regular languages
[Sip]: 193-197
-
Context-free languages
[Sip]: 198-200; [HU]: 137-138
-
A language of LBAs
[Sip]: 221-223
-
Closure properties
[HU]: 179-180
-
Language enumeration
[HU]: 170
-
Computation history based languages
[Sip]: parts of 223-226
-
Turing-recognizable languages
[HU]: 167-169, 180-181
-
Undecidability
-
The diagonal and universal languages
[Sip]: 206; [HU]: 182-183, 184-185
-
Mapping reductions
[Sip]: 234-236; [HU]: 185-188; [note]
-
Rice's theorems
[HU]: 188-190
-
Reductions using computation history
[Sip]: parts of 223-226
-
Post's Correspondance Problem
[HU]: 193-198, 200-201
-
Complexity classes
-
P
[Sip]: 275-276, 279-283, 284-291
-
NP, NP-hard, NP-complete
[Sip]: 283-284, 292-301, 304
-
A few popular NP-complete problems
[note] --- AR
-
PSPACE
[Sip]: 331-333, 336-339, 340; [HU]: 300-302
-
coNP
[HU]: 341-343; [note]
-
L, NL, coNL
[Sip]: 348-356
-
RP, ZPP, BPP
[note] --- not covered this time
-
Polynomial-time reductions
-
SAT → 3SAT → CLIQUE → VC
[Sip]: 302-303, 310-311
-
3SAT → HAMPATH → UHAMPATH
[Sip]: 314-319
-
3SAT → SUBSETSUM
[Sip]: 320-322
-
3SAT → 3DM; 3SAT → 3COL
[KT]: 481-485, 487-490
-
3DM → BINPACKING
[note] --- AR
-
The Cook-Levin theorem
[Sip]: 304-310
-
A PSPACE-hard problem: TQBF
[Sip]: 340-341
-
TQBF → FORMULA-GAME
[Sip]: 341-343
-
[HU]: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffrey D. Ullman, First Edition.
-
[Sip]: Introduction to the Theory of Computation by Michael Sipser, Third Edition.
-
Additional resources are provided where necessary.
-
AR stands for additional reading (no lecture delivered but included in syllabus).