Computer Science

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.
 NoteStudents are allowed only 1 retake of C S 252. This includes students who have failed or withdrawn (received a "W" grade). If after 1 retake, a student needs to retake the course again, the student must wait 1 semester/term before being allowed to take any C S course and must follow the petition process at This policy does not apply to classes dropped before the add/drop deadline. Petitions for exceptions to the policy can be completed at
 TaughtFall, Winter, Spring even years
 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.