Ad­van­ced Al­go­rithms

Lecturer: Prof. Dr. Christian Scheideler

Teaching Assistant: Maria Kokkou

Module information:

  • 6 ECTS Credits
  • Focus Area: Classical and Quantum Algorithm Design

Time and Location:

  • Lectures: Tue 08:15-10:45, F2.211
  • Tutorials: Mon 09:15-10:45, FU.511 (start in the third week)

Grading:

Prerequisites to be admitted to the oral exam are:

  • at least 40% of the points in the homework assignments and
  • presentation of a solution to a homework problem in the tutorials.

Two weeks will be reserved for the oral exams: Aug 3-7 and Sep 14-18.
Please ask my secretary 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 each Tuesday after the lecture. Solutions to the homework assignments can be submitted by teams of up to 3 members (please specify their names in the submission!). For each problem on a homework assignment you can get up to 2 points. (0: (mostly) wrong, 1: partially correct, 2: (almost) correct). If you want to present a solution to a homework problem in the upcoming tutorial, please drop a note in the "Homework Solutions" forum in PANDA. First come first serve. However, you should get 2 points for that problem in your submission to be eligible for the presentation.

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 April 30
  • Registration for qualifying participation: by May 27
  • Registration for exam in 1st phase: by May 27
  • Registration for exam in 2nd phase: by September 11