• There will be no tutorial on 25.01.19.
• There will be no exercises in the tutorial on 29.01.19. Instead, it will be open for questions. If you have any extensive or highly technical questions, please eMail these to Sascha Brauer (see box on the right) ahead of the tutorial.
• Lecture and tutorial will switch time slots in week 04/19 (see below).
• There will be no lecture on Tuesday the 15.01.19 due to the Tag der Lehre.
• The tutorials start in week 42, i.e. the first tutorial will be on 16.10.2018. Please bring your Laptop, or similar device, to the first tutorial.

Lecture

• Friday, 8-11 in F0.530

Tutorial

• Tuesday, 14-16 in F0.530

Exceptions

There are three exceptions to the schedule. The lecture and tutorial switch in weeks 44, 45, and 04/19. I.e. there will be

• a lecture on Tuesday, 30.10.18, 14-16 with a tutorial on Friday, 02.11.18, 9-11
• a lecture on Tuesday, 06.11.18, 14-16 with a tutorial on Friday, 09.11.18, 9-11
• (a lecture on Tuesday, 15.01.19, 14-16 [Lecture cancelled due to Tag der Lehre] with a tutorial on Friday, 18.01.19, 9-11)
• a lecture on Tuesday, 22.01.19, 14-16 (with a tutorial on Friday, 25.01.19, 9-11 [Tutorial cancelled])

There will be oral exams. Details on the exam period TBA.

Exam requirements

You are required to attain at least 50% of all possible homework points in order to participate in the exam.

Exam bonus steps

You can gain up to two bonus grade steps (e.g., improve your grade from 2,3 to 1,7). The bonus only applies if you pass the exam. You gain one step by attaining at least 60% of all possible homework points, and a second step by attaining at least 80% of all possible homework points.

Lecture: L.079.05512

Lecturer: Prof. Dr. Johannes Blömer

For detailed information please consult the Module Handbook.

[1] Michael R. Garey ; David S. Johnson: Computers and intractability: A Guide to the Theory of NP-Completeness. New York: Freeman, ISBN 0-7167-1044-7, 0-7167-1045-5

[2] Michael Sipser: Introduction to the Theory of Computation. 3. ed., Boston, MA.: Cengage Learning, ISBN 1-133-18779-X, 978-1-133-18779-0

[3] Sanjeev Arora ; Boaz Barak: Computational Complexity: A Modern Approach. New York: Cambridge University Press, ISBN 0-521-42426-7

[4] Oded Goldreich: Computational Complexity. Cambridge [u.a.]: Cambridge Univ. Press, ISBN 978-0-521-88473-0

[5] Christos H. Papadimitriou: Computational Complexity. Reading, Mass. [u.a.]: Addison Wesley, ISBN 0-02-015308-2, 0-201-53082-1

[6] Ingo Wegener: Komplexitätstheorie. Berlin [u.a.]: Springer, ISBN 3-540-00161-1

[7] Marcus Schaefer and Christopher Umans: Completeness in the Polynomial-Time Hierarchy: A Compendium. SIGACT News.