Introduction to the Theory of Computing - Stanford

Overview

Dive into the fundamental concepts of theoretical computer science through this comprehensive Stanford University course. Explore topics ranging from automata theory and formal languages to computability and complexity theory. Begin with an introduction to computing and proofs, then progress through deterministic and non-deterministic finite automata, regular expressions, and the pumping lemma. Delve into Turing machines, undecidability, and mapping reductions before tackling advanced subjects like complexity classes, NP-completeness, and the polynomial hierarchy. Conclude with discussions on space complexity, algorithmic fairness, and randomness, gaining a solid foundation in the theoretical underpinnings of computer science over approximately 20 hours of instruction.

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.