Apply     Visit     Give     |     Alumni     Parents     Offices     TCNJ Today     

CSC 445: Theory of Computation

Formerly CSC 460 “Theory of Computation”

Offered in Spring Semester

Course Units: 1

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