Core topics from finite Automata, languages and the theory of computation. The Chomsky hierarchy, abstract machines and their associated grammars. Models of computation (e.g., Turing machines), Church's thesis, unsolvability and undecidability. Computational complexity, intractability and NP-completeness.
Prerequisites: CSCI 2320, 1323, and junior standing.