As a result of the Corona crisis some course information may have altered. Do check your course announcements in Blackboard!

Algorithms and Complexity

Course Code :1001WETALC
Study domain:Computer Science
Academic year:2019-2020
Semester:2nd semester
Contact hours:60
Study load (hours):168
Contract restrictions: No contract restriction
Language of instruction:Dutch
Exam period:exam in the 2nd semester
Lecturer(s)Floris Geerts

3. Course contents *

The course starts by recalling Turing machines, and one-tape vs multi-tape, deterministic vs non-deterministic machines in particular. 

Using Turing machines as our computational model we next consider the concepts of space and time complexity. With regards to time complexity we concentrate on problems that are easy (below or in polynomial time) and those that are intrinsically hard (NP). The role of reduction is crucial in all this and we see many examples of reductions. The Theorem of Cook-Levin, in which the standard NP-complete problem is treated, will be considered. We also detail its proof.

With regards to space complexity, we consider PSPACE, NPSPACE, L and NL en see hard problems for each of these classes. We further see connections between these classes. We treat the Theorem of Savitch and the Theorem of  Immerman-Szelepcsenyi (and their proofs).

We conclude with PTIME-completeness.