[aduni.org logo] [classroom photo]

Home
A History of ADU
Courses
   One Course
Faculty and Alumni
Colloquia

Course Directory
Math SICP Disc
HCW OOP Alg
Sys Web ToC
AI DB Prob

FAQ  ||  donate  ||  USB drive


 Theory of Computation

[spacer]
   previous | next
 

InstructorShai Simonson

Course Description | Lectures and Courseware | Student Evaluations

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

Links

Here is are some course links from other schools: The homepage of the Hopcroft, Motwani and Ullman textbook. Solutions to many exercises and lots of other goodies.
Errata for the Sipser text.
The Java Computability Toolkit is a very nice Finite Automaton and Turing Machine simulator and it's free as well.
Pumping Lemma Poetry
More CS Poetry
Visual and interactive tools for learning CS theory


[horizontal rule]

Site last updated: May 14, 2013
Comments? Questions?

Creative Commons License

[spacer]