Advanced Algorithms

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.

Grading:

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 (marion.hucke@upb.de) for an appointment.

Contents:

The course will cover advanced topics on randomized algorithms.

• 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:

• Homework 1 (due Oct 18)
• Homework 2 (due Oct 25)
• Homework 3 (due Nov 8)
• Homework 4 (due Nov 15)
• Homework 5 (due Nov 22)
• Homework 6 (due Nov 29)
• Homework 7 (due Dec 6)
• Homework 8 (due Dec 13)
• There is no tutorial on Dec 20!
• Homework 9 (due Jan 10)
• Homework 10 (due Jan 17)
• Homework 11 (due Jan 24)

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: 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.