Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Course MAT-59-12-K-7

Probability and Algorithms (4V+2U, 9.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 9.0 CP 186 h
4 V Lecture 56 h
2 U Exercise class (in small groups) 28 h
(4V+2U) 9.0 CP 84 h 186 h

Basedata

SWS 4V+2U
CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. in WiSe
Level [7] Master (Advanced)
Language [EN] English
Lecturers
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Livecycle-State [NORM] Active

Contents

  • Deterministic and randomised algorithms – concepts,
  • Examples for randomised algorithms,
  • Erdös' probabilistic method – a construction principle for randomization,
  • Derandomisation strategies,
  • Azuma's inequality and the tailbound trick,
  • Probabilistic analysis of the traveling salesman problem,
  • Markov couplings and flows in Markov chains,
  • estimation of steady-state-approximation times and their application.

Literature

  • R. Motwani, P. Raghavan: Randomized Algorithms,
  • R. Bubley: Randomized Algorithms.

Materials

Further literature will be announced in the lecture; Exercise material is provided.

References to Course [MAT-59-12-K-7]

Module Name Context
[MAT-59-12-M-7] Probability and Algorithms P: Obligatory 4V+2U, 9.0 LP