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 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 cs.byu.edu/retake-policy. This policy does not apply to classes dropped before the add/drop deadline. Petitions for exceptions to the policy can be completed at cs.byu.edu/retake-policy.|
|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.