Written on 05.07.21 (last change on 05.07.21) by Markus Bläser
You can find details regarding the exams here: https://cms.sic.saarland/cct21/2/Exams
Written on 19.05.21 by Markus Bläser
Due to the holiday, there will be no lecture on Monday, May 24.
There will be a new assignment sheet, but with fewer exercises.
Complexity theory is the science of classifying problems with respect to their usage of resources. Ideally, we would like to prove statements of the form “There is an algorithm with running time O(t(n)) for some problem P and every algorithm solving P has to use at least Ω(t(n)) time”. But as we all know, we do not live in an ideal world
This lecture builds upon "Grundzüge der Theoretischen Informatik".
Time and Date:
- Monday, 10:15 - 12:00 (online)
- Wednesday 8:15 - 10:00 (online)
- First lecture: Wednesday, April 14
Lectures are live and will be recorded. The recordings will be made available after the lecture. The Zoom links are posted under "Materials".
- Thu 8:15 to 10:00 (online)
There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments. You can submit assignments in groups of up to three persons.
There will be oral exams at the end of the semester.
"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NP-completeness) is highly recommended.
There are many good books an the topic. Here is a selection:
- Sanjev Arora and Boaz Barak, Computational Complexity - A Modern Approach, Cambridge University Press.
- Oded Goldreich, Computational Complexity - A Conceptual Perspective, Cambridge University Press.
- Uwe Schöning, Gems of Theoretical Computer Science, Springer.
- Rüdiger Reischuk, Komplexitätstheorie (Band 1), Teubner.