Computability and Computational Complexity

This is a course in the theoretical foundations of computer science, centered around the theme of fundamental limits on computation. Topics include: Turing Machines, universal computation, undecidability of the halting problem, solvable and unsolvable algorithmic problems, recursive functions, Goedel's Incompleteness Theorem, time- and space-bounded computations, Cook's Theorem, NP-complete problems, problems solvable in polynomial space, randomized computation, application to cryptography, practical approaches to computationally intractable problems (such as SAT solvers), quantum computing, and Shor's Theorem.

Averages use numerical 1–5 ratings, including the ratings submitted with new anonymous reviews.

OrganizationHow well the course was organized

4.36 / 5

ChallengeHow intellectually challenging students found it

4.82 / 5

AttendanceHow necessary attendance was

4.46 / 5

AssignmentsHow helpful assignments were

4.62 / 5