CS 8041: Advanced Theory of Computation

3 Credit Hours
Prerequisite: Admission to Computer Science Ph.D. Program, Computer Science M.S. Program, or Analytics and Data Science Ph.D. Program
This course covers the fundamental and advance concepts of the theory of computing. The course covers models of computation, computability theory, both space and time complexity, and complexity classes. In particular, it introduces traditional models of computation, both operational, such as finite automata, pushdown automata, and Turing machines, and descriptive, such as propositional and predictive logic. It considers parallel and hierarchical state machines and more advanced models of computation, together with higher-order logics. Both time and space computational complexity are included together with the most relevant classes of complexity, and modern complexity-theoretic approaches such as algorithmic randomness and quantum complexity theory.