Randomized Algorithms (summer term 2014)

The course is given by Dr. Sabine Storandt. It takes place every Monday and Wednesday from 10:15am until 11:45am in the Hörsaal 03-26 in building 51.

Topics

- Las Vegas & Monte Carlo Algorithms

- Applications for Randomized Algorithms and Data Structures

- Improving Deterministic Bounds via Randomization

- Randomization in Games and AI

- Randomized Online Algorithms

- Probabilistic Method

Script

The complete script of the lecture (including further references) will be made available in the course svn repository.

The current version (last change: 05.05.14) of the script can be viewed here.

(The list of contents may still change during the course of the lecture.)

Dates

28.04. Introduction & Basic Stochastics notes
30.04. Las Vegas and Monte Carlo Algorithms: Analysis and Concentration Bounds, LV & MC for Max 3-SAT notes
05.05. k-Select, Approximative Median and Quick-Sort, Deterministic Sorting Lower Bound notes
07.05. Sorting Lower Bounds continued, Deterministic & Randomized Skip-Lists
12.05.
14.05. Exercise: Deterministic & Randomized Sorting in C++
19.05.
21.05.
26.05.
28.05.
02.06.
04.06.
16.06.
18.06.
23.06.
25.06.
30.06.
02.07.
07.07.
09.07.
14.07.
16.07.
21.07.
23.07.
28.07.
30.07.