C S 252
Download as PDF
Introduction to Computational Theory
Computer ScienceCollege of Computational, Mathematical, & Physical 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
Min
3
Fixed/Max
3
Fixed
3
Fixed
0
Other Prerequisites
C S 236 or concurrent enrollment.
Title
Understand Computing Paradigms
Learning Outcome
Understand the three computing paradigms (DFAs, PDA, Turing Machine) and their language-based equivalents. This study of the theoretical limits of computation is intellectually enlarging, as it reveals the fundamental laws and orderly patterns that govern all digital information.
Title
Categorize Problems
Learning Outcome
Categorize problems into one of the existing paradigms. This analytical process is character building, requiring the mental discipline and precision to correctly identify the inherent nature and constraints of a given challenge.
Title
Understand Paradigms
Learning Outcome
Understand the difference between and limitations of paradigms. Recognizing these boundaries fosters a sense of humility and spiritually strengthening wonder at the vastness of knowledge yet to be discovered and the complexity of the created world.
Title
Decidable and Tractable
Learning Outcome
Understand the difference between computable (decidable) and practically computable (tractable). Distinguishing between what is theoretically possible and what is practically achievable is intellectually enlarging, providing a realistic framework for professional decision-making.
Title
Solutions to Problems
Learning Outcome
Design and justify solutions to problems of decidability and tractability. Engaging with these deep, unresolved questions in computer science encourages a commitment to lifelong learning, as students prepare to contribute to the ongoing search for truth in their field.
