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: CS 191 - Computing Structures and MATH 198 - Analytic Geometry and Calculus I.
Credits: 3
NOTE:
* This course counts toward the 63-credit Liberal Arts and Sciences (LAS) graduation requirement.