Ad­vanced Al­gorithms

Lecturer: Prof. Dr. Christian Scheideler

Module information:

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

Time and Location:

  • Lectures: Fri 08:15-10:45, F0.530
  • Tutorials: Mon 16:15-17:45, F2.211 (start in the third week)

Grading:

Prerequisites to pass the course are:

  • presenting two solutions to a homework problem in the tutorial and
  • passing the oral exam at the end of the course.

Two weeks will be reserved for the oral exams: TBA and TBA.
Please ask Petra Schäfermeyer (petral@upb.de) for an appointment.

Contents:

The course will cover advanced topics on randomized algorithms. The lecture notes will be published in PANDA.

  • Chapter 1: Introduction
  • Chapter 2: Introductory Examples
  • Chapter 3: Online Algorithms
  • Chapter 4: Randomized Rounding
  • Chapter 5: Probability Amplification
  • Chapter 6: Randomized Metric Reduction
  • Chapter 7: Lowdimensional Optimization
  • Chapter 8: Approximate Counting

Homework assignments:

Will be posted in PANDA.

Literature:

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.

Remember:

  • Registration for modules and courses: by TBA
  • Registration for qualifying participation: by TBA
  • Registration for exam in 1st phase: by TBA
  • Registration for exam in 2nd phase: by TBA
Further information: