252-0209-00L  Algorithms, Probability, and Computing

Semester Autumn Semester 2017
Lecturers E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
Periodicity yearly course
Language of instruction English


Abstract Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction).
Objective Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Lecture notes Will be handed out.
Literature Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest;
Randomized Algorithms by R. Motwani und P. Raghavan;
Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf.