Building on the preliminaries established in CS 3133, this course explores fundamental questions of computability and complexity. Emphasis is on both mathematical foundations and applications to computing practice. Topics include the Church-Turing thesis, the halting problem, NP-completeness, time and space complexity classes, and related material as determined by the instructor. Students will be expected to read and write mathematical proofs.
Recommended Background
CS 3133.