Randomized Algorithms

Aims: 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)

Prerequisites: Algorithms and Data Structures 2; Mathematical Modelling 1 (or Probability Theory 1)

Compulsory programme: None

Capacity limit: None

Language: Danish or English

Contents: 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

Teaching: Weekly classes (2+2 hours)

Evaluation: Projects with individual evaluation, 13-scale

Credits: 5 ECTS

Quarter 3

Lecturer: Gudmund Skovbjerg Frandsen

Homepage: http://www.daimi.au.dk/~gudmund/RanAlg/

Text book: Not determined yet