The theory of computing, including finite automata, regular expressions and languages, context-free grammars and languages, push-down automata, pumping lemmas, the Chomsky hierarchy of language classes, Turing machines and computability, undecidability of the halting problem, reducibilities among decision problems and languages, time and space complexity, and NP-completeness and tractability.This is a first course on the theory of computing.
Introduction to Theory of Computing
Credit Hours:
4
Prerequisites:
CSCI (MATH) 2610 or CSCI 2611
Semester Offered:
Fall
Spring
Level:
Course Information File:
CIS_CSCI_2670_0.pdf
(216.67 KB)