CS 172. Computability and Complexity
Catalog Description: Finite automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness.
Units: 4
Related Areas:
Prerequisites: COMPSCI 170
Formats:
Fall: 3.0 hours of lecture and 1.0 hours of discussion per week
Spring: 3.0 hours of lecture and 1.0 hours of discussion per week
Grading Basis: letter
Final Exam Status: Written final exam conducted during the scheduled final exam period
Class Schedule (Fall 2025):
CS 172 – TuTh 12:30-13:59, Social Sciences Building 110 –
Avishay Tal
Class Notes
* Time conflicts ARE allowed but no alternate final exam.
* Lecture WILL be recorded for playback later.
Links: