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).
Lernziel
Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Skript
Will be handed out.
Literatur
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.
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Die Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodus
schriftlich 180 Minuten
Zusatzinformation zum Prüfungsmodus
There will be a written midterm exam and a written final exam. Script or any other supplementary material for either exam is not permitted. The grade of the midterm exam amounts to 20% and the grade of the final exam to 60% of the final grade. Extra reading material will be distributed and two special graded assignments - related to this reading material - handed out during the course. The grade of the special assignments amounts to 20% of the final grade.
Hilfsmittel schriftlich
Keine Hilfsmittel erlaubt.
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.