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: 12.05.14) of the script can be viewed here.

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

*****IMPORTANT: if you plan to take the exam, please send me an email until 23.05. (the words exam and randomized algorithms should appear in the subject)*****

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, Sorting Lower Bound notes

• 07.05. Sorting Lower Bounds continued, Deterministic & Randomized Skip-Listsnotes

• 12.05. Universal Hashingnotes

• 14.05. Exercise. Focus: Deterministic & Randomized Sorting notesexample code

• 19.05. Fingerprinting and Further Hashing Applications, Introduction to Samplingnotes

• 21.05. VC-dimension of Set Systems

• 26.05.

• 28.05. no lecture

• 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. test exam

• 30.07. test exam