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.