Theory Of computation Materials

Syllabus

Syllabus.pdf

Lecture Notes

Lecture_Notes.doc
Lecture_Notes.pdf

Lecture Videos

05-03-01: Finite State Machines
05-04-01: Closure and Nondeterminism
05-07-01: The Pumping Lemma
05-08-01: Minimizing FSMs
05-08-01: Recitation
05-09-01: Context Free Languages
05-10-01: CFLs and compilers
05-10-01: Recitation
05-11-01: Pushdown Machines
05-11-01: Recitation
05-14-01: CFGs and NPDMs
05-15-01: More lemmas, CYK
05-16-01: Undecidability and CFLs
05-16-01: Recitation
05-17-01: The Bullseye
05-18-01: Turing Machines
05-18-01: Recitation
05-20-01: The Halting Problem
05-21-01: Decidability
05-22-01: Complexity Theory, Quantified Boolean Formula
05-23-01: Savitch’s Theorem, Space Hierarchy
05-24-01: Decidability/Complexity Relationship, Recursion Theorem

Problem Sets

Problem_Set_01.html
Problem_Set_01_Solutions.html
Problem_Set_02.html
Problem_Set_02_Solutions.html
Problem_Set_03.pdf
Problem_Set_03_Solutions_Errata.txt
Problem_Set_03_Solutions.html
Problem_Set_04.pdf
Problem_Set_04_Solutions.html
Problem_Set_05.pdf
Problem_Set_05_Solutions.html

Exams

Exam_01.html
Exam_01.pdf
Exam_01_Solutions.html
Exam_02.pdf
Exam_02B.pdf

Handouts

Recitation_01.html
Recitation_02.html
Recitation_03.html
Recitation_03_1.gif
Recitation_03_2.gif
Recitation_03_3.gif
Recitation_03_4.gif
Recitation_03_5.gif
Recitation_03_6.gif
Recitation_03_7.gif
Recitation_04.html
Recitation_04_1.gif
Recitation_04_2.gif
Recitation_04_3.gif
Recitation_04_4.gif
Recitation_05.html
Recitation_06.html
Recitation_07.html
Recitation_08.html
Recitation_09.html