# Complexity Theory

## Prof. Dr. Markus Bläser

## Dr. Holger Dell

## Karteek Sreenivasaiah PhD

### News

- Room for the reexam is 007 in the bioinformatics building.
- There will be a tutorial on Wednesday Oct. 7, at 11:15 (room E1.3, 415) for re-exam preparation.
- If you would like to take the re-exam, please send an email to Markus Bläser.

### Topic

Complexity Theory is the science of classifying and sorting computational problems by its inherent difficulty.### Time & Date

- Mi 8:30 - 10:00, E1.3, HS1
- Fr 10:15 - 11:55, E1.3, HS1

- Friday 8-10, E1.3, SR16
- Tutor: Fabian Wobito, s9fawobi@stud...
- You can put your solutions in box 35 in E 2 5.

### Lecturer

**Prof. Dr. Markus Bläser**, Email: mblaeser at cs.uni-saarland...

Office Hours: whenever my office door is open, E 1 3, Room 412**Dr. Holger Dell**, Email: hdell@mmci...

Office Hours: whenever my door is open, E1.3, room 414**Karteek Sreenivasaiah PhD**, Email: karteek@mpi-inf.mpg.de

Office Hours: whenever my door is open, E1.3, room 422

### Prerequesites

- "Grundzüge der theoretischen Informatik" or something equivalent is helpful

### Grading

Exam dates:

Your final grade is the better grade of the two exams.

- End of term: Fri Aug 7, 9 -12, seminar room 14, E1.3
- Re-exam: Fri Oct 9, 9 - 12, room 007, bioinformatics building
- There will be no midterm

Your final grade is the better grade of the two exams.

Endterm grading:

- 36 points = 100%,
- 33 points = 90% = 1.3 (1.0 starts with 35 points)
- 29 points = 80% = 2.3 (30,31 = 2.0, 32 = 1.7)
- 23.5 points = 65% = 3.3 (25,26 = 3.0, 27, 28, = 2.7)
- 18 points = 50% = 4.0 (minimum pass mark) (22,23 = 3.7)

- 2542800, 40 points, 1.0
- 2536656, 35 points, 1.0
- 2550610, 33 points, 1.3
- 2549796, 33 points, 1.3
- 2543779, 24 points, 3.3
- 2519577, 18 points, 4.0
- 2557952, 11 points, 5.0

Re-exam results:

- 2549796, 31 points, no improvement
- 2550610, 24 points, no improvement
- 2557952, 17 points, 4.0

### Assignments

- Assignment 10 (corrected date of subm)
- Assignment 11
- Assignment 1 (optional, extra points)
- Assignment 2
- Assignment 3 (now without bugs)
- Assignment 4
- Assignment 5
- Assignment 6
- Assignment 7
- Assignment 8
- Assignment 9
- Sample assignments for the exam

### Script

### Literature

There are many good books on this topic. Here is a small selection

- Sanjev Arora and Boaz Barak,
**Computational Complexity - A Modern Approach**, Cambridge University Press. - Oded Goldreich,
**Computational Complexity - A Conceptual Perspective**, Cambridge University Press.