Complexity Theory
- Lecturer:
Prof. Dr. Ernst W. Mayr
- Module:
IN2007,
TUMonline
- Area:
4+2 lectures per week in
area III (Theoretical Computer Science)
core course, topic algorithms
- Time and Place:
Tuesday, 08:25–09:55, MI HS 2
Friday, 08:25–09:55, 00.13.009A
-
Exercises
2 hours per week exercises accompanying the lectures
Teaching Assistant: Chris Pinkau
- Exam:
The exam will take place on Th August 2, 2012 from 08:30 to 11:30
The mentioned time is the net process time. Please attend 15 minutes before.
The only permitted aid is an A4-page that contains notes written on both sides by your own hand. (Printers are not allowed.)
- Audience:
graduate students of computer science
students with computer science as minor
- ECTS: 8 Punkte
- Prerequisites:
1st and 2nd year courses
Course Efficient Algorithms and Datastructures I advantageous, but not required.
Course Randomized Algorithms advantageous, but not required.
- Recommended for:
Extended knowledge in complexity theory
- Slides:
And here is everything in one file!
(Hints for using the slides)
- Literature:
-
S. Arora, B. Barak:
-
Computational Complexity --- A Modern Approach
Cambridge University Press, 2009; text book
-
J.L. Balcázar, J. Díaz, J. Gabarró:
-
Structural Complexity I (and II)
EATCS Monographs, Springer-Verlag; accompanying
-
K.R. Reischuk:
-
Einführung in die Komplexitätstheorie
Teubner-Verlag; excerpts
-
Ch. Papadimitriou:
-
Computational Complexity
Addison-Wesley
-
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
-
Complexity and Approximation --- Combinatorial optimization problems and their approximability properties
Springer-Verlag
- Office Hours:
look here
