Introduction to Theory of Computing

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


Semester Offered: 
Course Information File: