C S 252
Introduction to Computational Theory
Computer Science
College of Physical and Mathematical Sciences
Course Description
Finite state automata, regular languages, lexical analysis; push-down automata, context-free languages, parsing; Turing machines and unrestricted grammars; computability complexity, NP-completeness.
When Taught
Fall and Winter
Grade Rule
Grade Rule 8: A, B, C, D, E, I (Standard grade rule)
Min
3
Fixed
3
Fixed
3
Fixed
0
Other Prerequisites
C S 236 or concurrent enrollment.
Title
Understand Paradigms
Learning Outcome
Understand the difference between and limitations of paradigms.
Title
Decidable and Tractable
Learning Outcome
Understand the difference between computable (decidable) and practically computable (tractable).
Title
Categorize Problems
Learning Outcome
Categorize problems into one of the existing paradigms.
Title
Solutions to Problems
Learning Outcome
Design and justify solutions to problems of decidability and tractability.
Title
Understand Computing Paradigms
Learning Outcome
Understand the three computing paradigms (DFAs, PDA, Turing Machine) and their language-based equivalents (regular languages,context-free languages, computable algorithms).
