Tik-79.240 Special Course on Computational Complexity

Fall 1998

Fall 1999

This is an advanced course on computational complexity covering topics such as NP-completeness, randomized algorithms, cryptography, approximation algorithms, parallel algorithms, polynomial hierarchy, PSPACE-completeness.

Teacher: Doc. Ilkka Niemelä
Lectures: Tuesdays 16-19, room T4 (in the new Computer Science Building)
Assistant: Tommi Junttila
Course material:
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
Brochure in Finnish.
Further information on how to pass the course.
Seminar program and home assignments
In order to get feedback from the home assignments that you have solved, please visit the assistant Tommi Junttila, on Tuesdays, 15.00-15.45, in room TB354 (in the new Computer Science Building).
Results of the home assignments
Guidelines for grading home assignments
See how the course grades are determined.
Slides for the introductory lecture by Ilkka Niemelä (PostScript; in Finnish)
Slides for a refresher on Boolean Logic by Ilkka Niemelä (PostScript; in English)
See also Chapter 4 in Papadimitriou's book.

Maintained by Ilkka.Niemela@hut.fi