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
Design of Computer ProgramsStanford University via Udacity Programming Languages
University of Virginia via Udacity Data Structures and Performance
University of California, San Diego via Coursera Introducción a Data Science: Programación Estadística con R
Universidad Nacional Autónoma de México via Coursera Applied Text Mining in Python
University of Michigan via Coursera