Introduction to Computational Theory
|Hours||3.0 Credit, 3.0 Lecture, 0.0 Lab|
|Prerequisites||C S 236 or concurrent enrollment.|
|Note||Students 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 cs.byu.edu/undergraduate-handbook/retake-policy-cs-courses/.|
|Taught||Fall, Winter, Spring even years|
|Programs||Containing C S 252|
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 into one of the existing 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.