Advanced Algorithms

You can use an A4 paper, written on both sides, for the exam. You can write whatever you want on it, but you are not allowed to use anything but your eyes to read it (glasses are of course OK). Make sure to bring an identification card. No cellular phones are allowed in the exam, nor calculators, or other electronic equipment.

Click here for the course material and exercise sheets.

This course deals with the fundamental theory behind algorithms and several advanced techniques for designing complex algorithms. The course starts with reviewing the basic models of computation, basic computability theory, the classes P and NP, and proof of NP-completeness of several interesting problems. We will then design approximation algorithms for many of these problems. We then study randomized algorithms and continue with a brief description of quantum algorithms.

This is an Master's course for students of the SIN and the SSC. The lectures and the exercises are offered in English only.

Current schedule:

• Course: Mondays, 10:15 - 11:45, INM202
• Course: Fridays, 10:15 - 11:45, INM200
• Exercises: Thursdays, 10:15 - 11:45, INM202

Classes start on 16.02.2009.

• Amin Shokrollahi, Fridays 09:00-10:00 at BC 110
• Frederic Didier, Wednesdays 10:00-11:00 at BC 128

• Michael Sipser, “Introduction to the Theory of Computation,” PWS Publishing Company, 1997.
• Christos Papadimitriou, “Computational Complexity,” Addison-Wesley, 1994.
• Michael Garey and David Johnson, “Computers and Interactibility: A Guide to the Theory of NP-Completeness,” Freeman and Company, 1979.
• Vijay Vazirani, “Approximation Algorithms,” Springer Verlag, 2001.
• Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms,” Cambridge University Press, 1995.