T-79.240 Special Course on Computational Complexity (3 cr)

Autumn 2002

[General Information] [Lectures] [Tutorials] [Home assignments] [TOPI]

Previous years: [Autumn 2001] [Autumn 2000] [Autumn 1999] [Autumn 1998]

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

• News: Course summary and feedback session on Thu Dec 5, 14-16, room A232
• Lectures by Prof. Ilkka Niemelä: Wednesday 14-17, room TB353
• Tutorials by Lic.Sc.(Tech.) Tommi Junttila: Thursdays 16-18, room B353
• The course starts on Wed Sep 11, 2002.
• Course material:
  C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. (Errata from the publisher, Some further Errata)
  
• Brochure in Finnish
• Program and seminar talks
• Practical arrangements for passing the course
• Extra bonus assignments

Lecture Notes

• Introduction to Computational Complexity
• Basics of Turing machines
• More on Turing machines, time and space complexity, undecidability
• Boolean logic
• Relations between complexity classes
• Reductions and completeness
• NP-complete problems
• coNP and function problems
• On P vs NP
• Parallel computation and logarithmic space

Tutorials

• Tutorials are held on Thursdays 16-18 in room TB353 by Tommi Junttila
• Tutorial exercises and their solutions

Home Assignments

• See the program for the home assignments for each week.
• See the practical arrangements for details about submitting and grading home assignments.
• Current point standings