Introduction to Computational Theory

Introduction to Computational Theory
Finite state automata, regular languages, lexical analysis; push-down automata, context-free languages, parsing; Turing machines and unrestricted grammars; computability complexity, NP-completeness.
 Hours3.0 Credit, 3.0 Lecture, 0.0 Lab
 PrerequisitesC S 236 or concurrent enrollment.
 TaughtFall, Winter
 ProgramsContaining C S 252
Course Outcomes

Understand Computing Paradigms

Understand the three computing paradigms (DFAs, PDA, Turing Machine) and their language-based equivalents (regular languages,context-free languages, computable algorithms).

Categorize Problems

Categorize problems into one of the existing paradigms.

Understand Paradigms

Understand the difference between and limitations of paradigms.

Decidable and Tractable

Understand the difference between computable (decidable) and practically computable (tractable).

Solutions to Problems

Design and justify solutions to problems of decidability and tractability.