COMPSCI 534 - Computational Complexity

Tuesday, January 8, 2013
2:00-5:00 pm
LSRC D106

Qualifying Exam Syllabus for COMPSCI 534 (formerly CPS 240)

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:

• Spring 2011
• Spring 2008
• Spring 2007

---

Return to qualifying exams main page