Introduction to computability, finite state machines, regular languages, context free grammars and parsing, Turing machines, complexity classes, applications including programming languages and compilers, network protocols, and natural language processing. Limits of computation. Quantum, hyper-computation and other models of computation.
Prerequisites: Minimum grade of C or better in CS 601 or CS 617, and CS 602, or permission of the graduate program director