There are many problems that can be solved more efficiently and by a
simpler algorithm, when we have free access to a source of random
bits, compared to when we have no such access.
The goal is that after the course the participants will
- know some prototypical examples of randomised algorithms
- be able to use basic tools from probability theory and probabilistic
analysis in the design and analysis of algorithms and data structures
- have experience in implementing randomised algorithms on standard
hardware (without access to truly random bits)
- Basic tools from probability theory and probabilistic analysis: Sums
of indicator variables; Game theoretic techniques and Yao's lower
bound technique; Tail inequalities in particular Chernoff bounds;
- Concrete examples of randomized algorithms and their analysis in a
representative selection of models and application areas taken from:
- Algorithmic models where randomization is / may be used: Monte Carlo
and Las Vegas algorithms, on-line algorithms and competitive analysis,
data structures, distributed algorithms, parallel algorithms, approximation
algorithms
- Application areas: graph algorithms, geometric algorithms, algebraic
algorithms, number theoretic algorithms, combinatorial optimization,
cryptography
Lecturer: Gudmund Skovbjerg Frandsen.
Teaching: Weekly classes (2 times 2 hours per week)
Text book: Motwani and Raghavan, Randomized
Algorithms. Cambridge University Press, 1995.
Homepage: http://www.daimi.au.dk/~gudmund/randomF05/
Prerequisites: Algorithms and Data Structures (1 and 2);
Probability Theory 1 or Mathematical Modelling 1
Compulsory programme: None
Capacity limit: None
Language: Danish or English.
Evaluation: Projects, 13-scale
Credits: 5 ECTS
Quarter 3rd (January 24 - March 11)