CSCI 435 - Theory of Computation

Credit(s): 3
Lecture Hours: 3
Lab Hours: 0
When Offered: Spring

A theoretical treatment of formal languages, classical models of computation, and related issues including complexity and computability. Topics include formal languages and the relationship among classes of languages; models of computation including regular expressions, grammars, finite state machines, and Turing machines; complexity classes (specifically P, NP, and NP-Complete) with connections to classical problems in computing; and the nature of decidable and undecidable problems.

Prerequisite(s): CSCI 302 and CSCI 325.