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 and MATH 198.
Credits: 3 hours
NOTE: This course counts toward the 63-hour Liberal Arts and Sciences (LAS) graduation requirement.