
T79.5103 
Computational Complexity Theory 
(5 cr) P 
Autumn 2005 (periods I and II)
[General Information]
[Lecture Notes]
[Tutorials]
[Homework]
[TOPI]
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
 Please use the TOPI
system for registration.
 This course replaces the former course
T79.240
Special Course in Computational Complexity.
 Lectures: Prof. (pro tem), D.Sc.(Tech.)
Tomi Janhunen,
Wednesdays, 1012, and
Thursdays (basically every 2nd week), 1012, room TB353
 Tutorials: M.Sc.(Tech.)
Matti Järvisalo,
Mondays, 1416, room TB353.
 Course material:
C. Papadimitriou:
Computational Complexity, AddisonWesley, 1994.
(Errata from the publisher,
some further corrections)
 Brochure in Finnish
 Program for lectures
and seminar talks
 Grades for the seminar presentations
 The topics of seminar talks were assigned on the 20th of October,
2005, using a protocol (a
series of lotteries). All topics have now been booked. If
there is still someone needing a topic he/she should contact
the lecturer urgently.
Back to menu.
Lecture Notes
(Slides in English)
Please remember to check the tentative schedule for presenting this material.
In particular, there are exceptional Thursdays as no lecture is given.
Back to menu.
Course Feedback
We welcome feedback which is collected centrally in
Finnish,
Swedish, or
English;
the questionnaire is activated on the 9th of December, 2005.
 To obtain a 0.5 point
homework bonus
you are supposed to fill in the form by
the 2nd of January, 2006 (24:00 hours).
Back to menu.
Tutorials
Back to menu.
Homework
 Weekly homework is based on
selected exercises
from Papadimitriou's book.
 Please note that homework exercises are personal and
thus copying answers (plagiarism) is prohibited!
Back to menu.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 05 January 2006.
Tomi Janhunen
