Theory of Computation, Fall 2020

Theory of Computation, Fall 2020

MIT open courseware via YouTube Direct link

1. Introduction, Finite Automata, Regular Expressions

1 of 25

1 of 25

1. Introduction, Finite Automata, Regular Expressions

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Theory of Computation, Fall 2020

Automatically move to the next video in the Classroom when playback concludes

  1. 1 1. Introduction, Finite Automata, Regular Expressions
  2. 2 2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
  3. 3 3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
  4. 4 4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
  5. 5 5. CF Pumping Lemma, Turing Machines
  6. 6 6. TM Variants, Church-Turing Thesis
  7. 7 7. Decision Problems for Automata and Grammars
  8. 8 8. Undecidability
  9. 9 9. Reducibility
  10. 10 10. Computation History Method
  11. 11 11. Recursion Theorem and Logic
  12. 12 12. Time Complexity
  13. 13 14. P and NP, SAT, Poly-Time Reducibility
  14. 14 15. NP-Completeness
  15. 15 16. Cook-Levin Theorem
  16. 16 17. Space Complexity, PSPACE, Savitch's Theorem
  17. 17 18. PSPACE-Completeness
  18. 18 19. Games, Generalized Geography
  19. 19 20. L and NL, NL = coNL
  20. 20 21. Hierarchy Theorems
  21. 21 22. Provably Intractable Problems, Oracles
  22. 22 23. Probabilistic Computation, BPP
  23. 23 24. Probabilistic Computation (cont.)
  24. 24 25. Interactive Proof Systems, IP
  25. 25 26. coNP is a subset of IP

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.