Advanced Algorithms

Lecture notes and exercise sheets can be found at the Moodle page of the course (to enroll, you need a one-time enrollment key that is announced in the course).

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 and Groebner bases.

This is an Master's course for students of the SIN and the SSC. It is required for Master's students of SIN who specialize in Foundations of Software. It is optional for students of the SSC, and replaces the previously offered course “Selected Topics in Algorithms”. The lectures and the exercises are offered in English only.

At each lecture one student is selected to take notes of the course, type it up in LaTeX, and provide it on the website of the course. In addition, students may be required to give short presentations in the exercise sessions. There will be no midterm, only one final exam. The grade will be composed of the scribe notes, the presentations, and the final exam.

Current schedule:

  • Courses: Tuesdays and Thursdays, 10:00 - 12:00, INM010
  • Exercises: Fridays, 14:00 - 16:00, INM010
  • Classes start on 24.10.2006.

Suggested reading:

  • 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.
  • David Cox, John Little, and Donal O'Shea, “Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra,” Springer Verlag, 1996.
  • Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms,” Cambridge University Press, 1995.