Formerly CSC 460 “Theory of Computation”
Offered Every Spring
Course Units: 1
Description:
This course focuses on the traditional, algorithmic theory of computation consisting of three subareas: (1) computability, (2) complexity theory, and (3) formal languages and automata. Topics include: finite automata, regular expressions/languages, push-down automata, context-free grammars/languages, Turing machines, Church-Turing thesis, decidability/undecidability, reducibility, and time/space complexity including NP-completeness.
Prerequisite notes: CSC 230, 270 and MAT 127, each with a grade of C or better, and CSC 335.
Required for major/minor: Computer Science Major
Option for major/minor: Computer Science Minor