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%).

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).

Lecture Notes

• Practical arrangements [ps] [pdf]
• Examples of Problems [ps] [pdf]
• Turing Machines [ps] [pdf]
• More about Turing Machines [ps] [pdf]
• Boolean Logic [ps] [pdf]
• Relations between Complexity Classes [ps] [pdf]
• Reductions and Completeness [ps] [pdf]
• NP-complete problems [ps] [pdf]
• coNP and function problems [ps] [pdf]

Tutorials

• Tutorials are held on Mondays 14-16 by Matti Järvisalo.
• Tutorial schedule with solutions

Homework

• Home assignment schedule with instructions and grading