Introduction to the Theory of Computing - Stanford
Offered By: Stanford University via YouTube
Course Description
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.
Taught by
CS 154 - Introduction to the Theory of Computing
Tags
Related Courses
Towards an Ethical Digital Society: From Theory to PracticeNPTEL via Swayam Fairness in Medical Algorithms - Threats and Opportunities
Open Data Science via YouTube Fairness in Representation Learning - Natalie Dullerud
Stanford University via YouTube Privacy Governance and Explainability in ML - AI
Strange Loop Conference via YouTube AI UK - Doing Better in Data Science – From Algorithmic Fairness to Diversity
Alan Turing Institute via YouTube