Overview
Syllabus
1 computing.
2 curriculum.
4 proofs.
5 DFA Overview.
6 DFA.
7 DFAClosure1.
8 NFA.
9 NFA2DFA.
10 DFA Closure2.
11 RegExp.
12 pumping.
13 minimizingDFA.
14 Myhill Nerpde.
15 learning DFA.
16 Streaming.
17 CC.
18 TM overview.
19 TM.
20 TM variants.
21 Universal TM.
22 counting argument.
23 concrete undecidable.
24 mapping reductions.
25 rices theorem.
26 oracle reductions.
27 self reference.
28 logic.
29 Kolmogorov Complexity.
30 complexity overview.
31 time complexity.
32 NP.
33 poly time reductions.
34 Cook Levin.
35 more NPC.
36 co NP.
37 polynomial hierarchy.
38 space complexity.
39 Proofs++.
40 Algortihmic Fairness.
41 Randomness.
42 Parting thoughts.
Taught by
CS 154 - Introduction to the Theory of Computing