Ad­vanced Al­gorithms

Lecturer: Prof. Dr. Christian Scheideler

Module information:

  • 6 ECTS Credits
  • Focus Area: Algoirthm Design
  • Modelle und Algorithmen (MuA)

For those students that just want to take the 4 ECTS variant of the course: only the contents taught till the December 17 will be relevant for the exam. Please inform the lecturer if you want to make use of this option.

Time and Location:

  • Lectures: Di 8-11, F0.530
  • Tutorials: Fr 16-18, F0.530

There won't be a tutorial on Jan 31.


Prerequisites to pass the course are:

  • presenting a solution to a homework problem in the tutorial and
  • passing the oral exam.

Two weeks have been reserved for the oral exams: February 10-14 and March 25-27. Please ask Marion Hucke ( for an appointment.


The course will cover advanced topics on randomized algorithms.

Homework assignments:


The lecture will be based on research papers that are cited in the lecture notes. Books that give or contain an introduction to randomized algorithms (and are covering some parts of the lecture) are, for example:

  • Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  • Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Second Edition). Cambridge University Press, 2017.
  • Juraj Hromkovic. Randomisierte Algorithmen. Teubner Verlag, 2004.
  • Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson Education, 2006.
  • Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1994.
  • Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Interscience Series in Discrete Mathematics and Optimization, 2000.


  • Registration for modules and courses: till 25.10.
  • Registration for qualifying participation: 21.10.-21.11.
  • Registration for exam in 1st phase: 21.10.-21.11.
  • Registration for exam in 2nd phase: 02.03.-06.03.
Further information: