Course Detail
Units:
3.0
Course Components:
Lecture
Enrollment Information
Enrollment Requirement:
Prerequisites: "C-" or better in (CS 3100 AND CS 4150) AND Full Major status in Computer Science OR Computer Engineering.
Description
Meets with CS 6100. A survey of topics in theoretical computer science, focusing on computability and complexity. Turing machine, decidability, relative computability, recursion theorem, non-deterministic TMs, complexity measures, time and space hierarchies, P and NP, NP-completeness, program specification and verification. Undergraduate students only.