Prerequisite: CPSC 131 and MATH 270B or MATH 280, declared major/minor in CPSC, CPEN, or CPEI. Introduction to the theory of computation. Automata theory; finite state machines, context free grammars, and Turing machines; hierarchy of formal language classes. Computability theory and undecidable problems. Time complexity; P and NP-complete problems. Applications to software design and security.