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. Enrollment Requirements: Prerequisites: "C-" or better in (CS 3100 AND CS 4150) AND Full Major status in Computer Science OR Computer Engineering.