Theory of Computation: Automata and language theory: regular and context free languages; finite state automata and pushdown automata; regular expressions; pumping lemmas. Computability theory: Turing machine and its variants; decidability and reductions; recursive, recursively enumerable (r.e.), and non-r.e. languages. Complexity theory: time complexity and NP-completeness; a survey of NP-complete problems; space complexity and PSPACE-completeness.