|
T-79.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 NP-completeness, randomized algorithms, cryptography,
approximation algorithms, parallel algorithms, polynomial hierarchy,
PSPACE-completeness.
General Information
- Please use the TOPI
system for registration.
- This course replaces the former course
T-79.240
Special Course in Computational Complexity.
- Lectures: Prof. (pro tem), D.Sc.(Tech.)
Tomi Janhunen,
Wednesdays, 10-12, and
Thursdays (basically every 2nd week), 10-12, room TB353
- Tutorials: M.Sc.(Tech.)
Matti Järvisalo,
Mondays, 14-16, room TB353.
- Course material:
C. Papadimitriou:
Computational Complexity, Addison-Wesley, 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
|