This information sheet indicates how the course will be organized at pandemic code level yellow and green.
If the colour codes change during the academic year to orange or red, modifications are possible, for example to the teaching and evaluation methods.

Algorithms and Complexity

Course Code :1001WETALC
Study domain:Computer Science
Academic year:2020-2021
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.