CS 611 - Theory of Computation

Units: 3
Alphabets, strings and languages, regular languages and finite automata, context-free languages, grammars, context-sensitivity, Turing machines and Turing-Completeness, decidability, Church-Turing thesis, reducibility, time and space complexity classes, P versus NP, NP-Completeness and NP-Hard problems.

Prerequisites: CS 411 or M.S. Computer Science major.
Credit Restrictions: Computer Science M.S. or B.S. students only.
Equivalent Quarter Course: CS 6260.
Possible Instructional Methods: Entirely On-ground.
Grading: A-F grading only.
Student Learning Outcomes - Upon successful completion of this course students will be able to:

Construct formal models of computation such as DFAs, CFGs, and Turing machines to describe various languages.
Develop complex proofs to statements regarding the complexity of languages.
Determine whether novel languages are decidable, acceptable, or undecidable.
Convert a problem to an equivalent formal representation.
Prove that a complex problem is NP-Complete.