Theory of Computation

Catalog description

The course investigates two fundamental questions about computing: 1) computability: can a problem be solved using a given abstract machine? And 2) complexity: how much time and space are required to solve the problem? The course explores these questions by developing abstract models of computation and reasoning about what they can do and cannot do efficiently. The abstract models include finite automata, regular languages, context- free grammars, and Turing machines. Additional topics covered include solvable and unsolvable problems, complexity classes P and NP, and NP- completeness. Three credits; one-hour laboratory. The pre requisite of AI 230 is required.