Theory of Algorithms (COMP512)
Automata, languages, complexity, computability. Finite automata, 2-head finite automata, pushdown automata, Turing machine. Chomsky hierarchy. Time complexity: class P, NP, NP completeness, NP complete problems. Space complexity: Savitch theorem, class PSPACE. Hierarchy theorems and circuit complexity.