
T79.5103 
Computational Complexity Theory 
(5 cr) P 
Autumn 2006 (periods I and II)
[General Information]
[Lecture Notes]
[Tutorials]
[Homework]
[TOPI]
Previous years:
[Autumn 2005]
This is an advanced course on computational complexity covering topics
such as NPcompleteness, randomized algorithms, cryptography,
approximation algorithms, parallel algorithms, polynomial hierarchy,
PSPACEcompleteness.
General Information
 (14.12.) NEWS: Bonus points
 Please use the TOPI
system for registration.
 This course replaces the former course
T79.240
Special Course in Computational Complexity.
 Lectures: Prof.
Ilkka Niemelä,
Tuesdays, 1012, and
Wednesdays, 1012, room TB353
 Tutorials: M.Sc.(Tech.)
Matti Järvisalo,
Mondays, 1416, room TB353.
 The course starts on Tue Sep 19 at 10 o'clock in TB353.
 Course material:
C. Papadimitriou:
Computational Complexity, AddisonWesley, 1994.
(Errata from the publisher,
some further corrections)
 Brochure in Finnish
 In order to pass the course one needs to pass three compulsory
parts:
 the first quarter exam (Oct 3; Chapter 13 in the Papadimitriou book).
 homework assignments (11 rounds, 1st round Oct 13)
 seminar presentation
 The topics of seminar talks are assigned on Oct 24, using a protocol (a
series of lotteries).
 Program for lectures and seminar talks
 Seminar talk practice
 Final grading of the seminar talks
 Course points and final grading
 The grade of the course (05) is determined by the respective grades
of
 the first quarter exam (15%),
 the homework (70%) and
 the seminar talk (15%).
Back to menu.
Course Feedback
We welcome feedback which is collected centrally in
Finnish,
Swedish,
and
English.
The questionnaire is activated on December 13, 2006.
 To obtain a 0.5 point
homework bonus
you are supposed to fill in the form by
the 3rd of January, 2006 (24:00 hours).
Please remember to supply your student ID on the
form. This is just to collect the list of students who have given
feedback (anonymity is not otherwise compromised).
Back to menu.
Lecture Notes
(Slides in English; to appear as the course proceeds)
Back to menu.
Tutorials
Back to menu.
Homework
Back to menu.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 22 February 2007.
Ilkka Niemelä
