MIT 18.404J Theory of Computation, Fall 2020 (English)

   Tuesday, December 03, 2024   

Starting a new Lecture Notes Series on MIT 18.404J Theory of Computation, Fall 2020

Youtube Lecture Playlist Credits 

Channel Name: MIT OpenCourseWare

So Let Us Start to This Journey of Learning 

MIT 18.404J Theory of Computation, Fall 2020 By Lecture Notes together!

Lecture 1: 1. Introduction, Finite Automata, Regular Expressions

Lecture 2: 2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

Lecture 3: 3. Regular Pumping Lemma, Conversion of FA to Regular Expressions

Lecture 4: 4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

Lecture 5: 5. CF Pumping Lemma, Turing Machines

Lecture 6: 6. TM Variants, Church-Turing Thesis

Lecture 7: 7. Decision Problems for Automata and Grammars

Lecture 8: 8. Undecidability

Lecture 9: 9. Reducibility

Lecture 10: 10. Computation History Method

Lecture 11: 11. Recursion Theorem and Logic

Lecture 12: 12. Time Complexity

Lecture 13: 14. P and NP, SAT, Poly-Time Reducibility

Lecture 14: 15. NP-Completeness

Lecture 15: 16. Cook-Levin Theorem

Lecture 16: 17. Space Complexity, PSPACE, Savitch's Theorem

Lecture 17: 18. PSPACE-Completeness

Lecture 18: 19. Games, Generalized Geography

Lecture 19: 20. L and NL, NL = coNL

Lecture 20: 21. Hierarchy Theorems

Lecture 21: 22. Provably Intractable Problems, Oracles

Lecture 22: 23. Probabilistic Computation, BPP

Lecture 23: 24. Probabilistic Computation (cont.)

Lecture 24: 25. Interactive Proof Systems, IP

Lecture 25: 26. coNP is a subset of IP