Theory of Computation (MIT 18.404)

Advanced Computer Science by Free Academy. 25 lectures, 32.3 hours. Covers: automata regular languages context free grammars turing machines decidability complexity p vs np.

Lectures

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

Quick explainers

All courses