
T79.5103 
Computational Complexity Theory 
(5 cr) P 
Autumn 2007 (periods I and II)
Previous years:
[Autumn
2005]
[Autumn 2006]
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
 (17.1.) NEWS:
Final grading summary available below.
 Please use the WebTOPI
system for registration.
 This course replaces the former course
T79.240
Special Course in Computational Complexity.
 Lectures: Prof.
Ilkka Niemelä,
Mondays, 1012, and
Wednesdays, 1012, room TB353
(see the lecture
program for exceptions).
 Tutorials: Lic.Sc.(Tech.)
Matti Järvisalo,
Mondays, 1416, room TB353 (see the tutorial
program for exceptions).
 The course starts on Mon Sep 17 at 10 o'clock in TB353.
 Course material:
C. Papadimitriou:
Computational Complexity, AddisonWesley, 1994.
(Errata from the publisher,
some further corrections)
 Brochure in Finnish
 Grading: First part exam (20%), three home assignments
(40%), second part exam (40%)
 Summary of the grading in Autumn 2007 [pdf]
Course Program
Course Feedback
We welcome feedback which is collected centrally in
Finnish,
Swedish,
and
English.
The questionnaire is open from December 10 to January 7, 2008.
 To obtain a 0.5 point
homework bonus
you are supposed to fill in the form by
January 7, 2007 (23:59 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.
Further Reading
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 17 January 2008.
Ilkka Niemelä
