Exam is closed book.
Abstract Computing Models:
- Finite State Automata and Regular Languages
- Context Free Grammars Push Down Machines
- Turing Machines and Counter Machines
Recursion Theory:
- Recursive and Recursively Enumerable Languages
- Undecidable Langauges, Diagonalization Proofs, Reducability
- Church-Turing Thesis, Halting Problem
Computational Complexity Theory:
- Complexity Measures
- Complexity Classes
- Turing Machine Time and Space Complexity Classes
Intractability:
- Polynomial Time and Log-Space Reductions
- NP, NP-Completeness, and co-NP
- PSPACE Complete Problems
Suggested Readings:
- J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison Wesley
- J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley
- M. Sipser, Introduction to the Theory of Computataion, PWS Publishers
Sample Exams: