Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Module MAT-59-12-M-7

Probability and Algorithms (M, 9.0 LP)

Module Identification

Module Number Module Name CP (Effort)
MAT-59-12-M-7 Probability and Algorithms 9.0 CP (270 h)

Basedata

CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. in WiSe
Level [7] Master (Advanced)
Language [EN] English
Module Manager
Lecturers
Area of study [MAT-OPT] Optimisation
Reference course of study [MAT-88.105-SG] M.Sc. Mathematics
Livecycle-State [NORM] Active

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U MAT-59-12-K-7
Probability and Algorithms
P 84 h 186 h - - PL1 9.0 WiSe
  • About [MAT-59-12-K-7]: Title: "Probability and Algorithms"; Presence-Time: 84 h; Self-Study: 186 h

Examination achievement PL1

  • Form of examination: oral examination (20-30 Min.)
  • Examination Frequency: each semester
  • Examination number: 86371 ("Probability and Algorithms")

Evaluation of grades

The grade of the module examination is also the module grade.


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.

Competencies / intended learning achievements

Upon successful completion of this module, the students have familiarized themselves with different types of randomized algorithms. They are able to evaluate the complexity and efficiency of randomized algorithms and to apply examples of randomized algorithms to solve problems of mathematical optimization.

Through case studies, the students have learnt to perform a probabilistic analysis of algorithms and to apply methods based on Markov chains. They understand the proofs presented in the lecture and are able to comprehend and explain them. In particular, they are able to outline the conditions and assumptions that are necessary for the validity of statements.

Literature

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

References to Module / Module Number [MAT-59-12-M-7]

Course of Study Section Choice/Obligation
[INF-88.79-SG] M.Sc. Computer Science Specialization 1 [WP] Compulsory Elective
Module-Pool Name
[MAT-52-MPOOL-7] Specialisation Mathematical Optimisation (M.Sc.)
[MAT-AM-MPOOL-7] Applied Mathematics (Advanced Modules M.Sc.)
[MAT-RM-MPOOL-7] Pure Mathematics (Advanced Modules M.Sc.)