This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
MA5208 is a semester module in English language at Master’s level which is offered irregular.
This module description is valid from SS 2012 to SS 2012.
|Total workload||Contact hours||Credits (ECTS)|
|150 h||45 h||5 CP|
Content, Learning Outcome and Preconditions
In this course we first focus on the binomial G(n,p) model and investigate some of the phase transitions in its evolution. We then switch to more complicated models for constrained random graphs, such as random trees and random regular graphs. Finally, we analyse randomized algorithms and the expected performance of deterministic algorithms for several optimization problems.
The underlying probabilistic methods comprise: First and Second Moment, Large Deviation Inequalities, Generating Functions, Markov Chains.
They are able to use these properties to design and analyse the performance of algorithms for some of the classical optimization problems.
Courses, Learning and Teaching Methods and Literature
Learning and Teaching Methods
B. Bollobas: Random Graphs. Cambridge University Press, 2001.
P. Flajolet and R. Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009.
S. Janson, T. Luczak, and A. Rucinski: Random Graphs. Wiley, 2000.
R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.