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 1 repeat of each C S undergraduate course (all 100-, 200-, 300- or 400-level courses). This includes all students who received any grade including those who withdraw (receive a "W" grade) from a C S course. Students must wait 1 semester/term before being allowed to take a course they have failed twice. 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.