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

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

Exam

The oral exam takes place at 26.08.2014. If you want to take the exam but the date is impossible for you, please write a mail.

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 & Epsilon-Nets notes

• 26.05. Exercise + Good Random Samples for Systems with Small VC-dimension and Epsilon-Nets notes

• 28.05. no lecture

• 02.06. Good Hitting Set Approximations notes

• 04.06. Route Planning and Epsilon-Nets notes

• 16.06. Exercise. Focus: Hitting Sets for Road Networksnotesexample code

• 18.06. The Closest Pair problemnotes

• 23.06. The Min Cut problemnotes

• 25.06. Sublinear Algorithmsnotes

• 30.06. Long Path problems + Exercise (Min Cut and Connected Components)

• 02.07.
• 07.07.
• 09.07.
• 14.07.
• 16.07.
• 21.07.
• 23.07.

• 28.07. test exam

• 30.07. test exam