نظریه محاسبات

این دوره متشکل از ۶ عدد cd ، با جزئیات زیر است.

علاوه بر این در این دوره به موضوعاتی از جمله کامپایلر‌ها ، جستجو بر روی متون نیز پرداخته می شود، به علاوه مسائلی از جمله finite state machines, pushdown machines, context free grammars and Turing machines مورد تحلیل قرار می گیرند.

این دوره شامل ۲۲ جلسه به صورت زیر است :

1. Finite State Machines

2. Closure and Nondeterminism

3. The Pumping Lemma

4. Minimizing FSMs

5. Recitation

6. Context Free Languages

7. CFLs and compilers

8. Recitation

9. Pushdown Machines

10. Recitation

11. CFGs and NPDMs

12. More lemmas, CYK

13. Undecidability and CFLs

14. Recitation

15. The Bullseye

16. Turing Machines

17. Recitation

18. The Halting Problem

19. Decidability

20. Complexity Theory, Quantified Boolean Formula

21. Savitch's Theorem, Space Hierarchy

22. Decidability/Complexity Relationship, Recursion Theorem