YoVDO

Introduction to the Theory of Computing - Stanford

Offered By: Stanford University via YouTube

Tags

Computer Science Courses Regular Expressions Courses Computational Models Courses Finite Automata Courses Turing Machines Courses Complexity Theory Courses Algorithmic Fairness Courses

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 Practice
NPTEL 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