CS 291 - Models of Computation

Logic: propositional calculus, first-order predicate calculus. Formal reasoning: natural deduction, resolution. Applications to program correctness and automatic reasoning. Formal models of computation: regular languages, finite automata, grammars, pushdown automata, Turing machines, classes P and NP, uncomputability, the halting problem.

Prerequisites: A grade of C or better in CS 191 - Computing Structures and completion of MATH 198 - Analytic Geometry and Calculus I.
Credit(s): 3