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).
Learning 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.
Performance assessment
Performance assessment information (valid until the course unit is held again)
The performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examination
written 180 minutes
Additional information on mode of examination
There will be an optional written midterm exam and a written final exam. Script or any other supplementary material for either exam is not permitted. Furthermore, we will hand out two special assignments (compulsory continuous performance assessment) whose solution (typeset in LaTeX) is due two weeks later and will be graded.
The final grade is 20% midterm exam + 20% special assignments + 60% final exam OR if the result of the midterm exam does not improve the final grade or has not been sitted: 20% special assignments + 80% final exam
Written aids
Keine Hilfsmittel erlaubt.
This information can be updated until the beginning of the semester; information on the examination timetable is binding.
Performance assessment as a semester course