- Theory of Computation

Catalog description

This course will continue from where CS 234 left off in studying computers as mathematical abstractions to understand the limits of computation. In this course, students will learn about topics in computability theory and complexity theory. Topics in computability theory include Turing machines and their variations, the Universal Turing machine, decidability of the halting problem, reductions, and proving the decidability of other problems. Topics in complexity theory include the classes P and NP, NP-completeness, and other fundamental complexity classes. The Department strongly recommends that students enrolling in this course have earned a grade of C or higher in Data Structures ( CS 271 ). This course is classified as a theory elective.