TCS / Studies / T-79.5103 Computational Complexity Theory
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science


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 NP-completeness, randomized algorithms, cryptography, approximation algorithms, parallel algorithms, polynomial hierarchy, PSPACE-completeness.

General Information

  • (14.12.) NEWS: Bonus points
  • Please use the TOPI system for registration.
  • This course replaces the former course T-79.240 Special Course in Computational Complexity.
  • Lectures: Prof. Ilkka Niemelä, Tuesdays, 10-12, and Wednesdays, 10-12, room TB353
  • Tutorials: M.Sc.(Tech.) Matti Järvisalo, Mondays, 14-16, room TB353.
  • The course starts on Tue Sep 19 at 10 o'clock in TB353.
  • Course material: C. Papadimitriou: Computational Complexity, Addison-Wesley, 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 1-3 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 (0-5) 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.


Back to menu.


Back to menu.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 22 February 2007. Ilkka Niemelä