Course:
Course Program:
Basic concepts of computation. The theory and representation of algorithms and models of computation. Computability and recursive functions. Formal specification and proofs of programs. Automata theory.
Prerequisite:
CmpE 350
Topics (subject to change):
1. Reducibility
2. Advanced Topics in Computability Theory
3. Complexity Theory
Textbook:
Michael Sipser. Introduction to the theory of Computation, 3nd ed.