Introduction to basic mathematical models of computation and the finite representation of infinite objects. Finite automata, regular languages, non-determinism, pushdown automata, context-free languages, Turing machines and variants, halting problem, time complexity of algorithms, and NP-complete problems. Prerequisites: MTH 325, CS 162, and CIS major standing. Three credits.
Taught this Fall by: |
|