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.