Introduction to theoretical study of computability and efficient computation. Finite-state and pushdown automata; Turing machines and the Church-Turing thesis; undecidability; computational complexity; NP-completeness. Prerequisite: COSC 3020.