3 Credits Turing machines, the Church-Turing thesis, decidability, the halting problem, reducibility, recursive function theory, the recursion theorem, time and space complexity, classes P and NP, NP-completeness.
Prerequisites CS 420 with a C or better or CS 520 with a C or better