This course covers the fundamentals of the theory of computing, including topics such as proofs, deterministic and non-deterministic finite automata, regular expressions, Turing machines, complexity theory, and algorithmic fairness. Students will learn how to analyze and prove properties of computational systems, understand different computational models, and explore the limits of what can be computed. The course uses a combination of lectures, problem-solving sessions, and theoretical exercises to help students develop their analytical and problem-solving skills. This course is intended for students with a basic understanding of computer science concepts and an interest in theoretical aspects of computing.
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
