CSCI 383 - Theory of Computer Science

3 NS, QPf
Second Semester. A study of computability, enumerability, and decidability from a machine approach (finite state automata, push-down automata, Turing machines), a language approach (regular grammars, context-free grammars, unrestricted rewrite systems, the Chomsky hierarchy), and the recursive function approach. In the final weeks of the semester, the theory of NP-Completeness will be discussed, along with the notion of reductions and Cook’s theorem.

Prerequisites & Notes
Prerequisite: MATH 220 or consent of the instructor.
Mr. Geitz

Credits: 3 hours