CS 475 Introduction to the Theory of Computing

This is a first course on the theory of computing. Topics covered include finite automata, regular expressions and languages, push-down automata, pumping lemmas for regular and context-free grammars, the Chomsky hierarchy of language classes, Turing machines and computability, the decidability of the halting problem, time complexity and NP-completeness and tractability.

Credits

3

Prerequisite

CS 372 (Data Structures) and MA 308 (Discrete Mathematics)