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: 08.07.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.

Question Time

==> Monday, 04.08. at 16:15 and Monday, 25.08. at 10:15 (Hörsaal 03-26 in building 51). Please come prepared, i.e. read through the script before and tell me explicitly what is unclear or where you need additional explanations. The final script as well as a catalogue of possible exam questions will be made available before.

Dates

1. Preliminaries

• 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

2. Randomized Algorithms and Data Structures

• 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

• 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

3. Getting Beyond Deterministic Bounds via Randomization

• 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)notesexample code connected componentsexample code min cut

4. Randomization in AI

• 02.07. Exercise (Min Cut ctd. and Long Path) + The Cow Path Problem notes

• 07.07. Robot Navigation in Unknown Terrain: Deterministic Algorithmsnotes

• 09.07. Robot Navigation in Unknown Terrain: Randomized Algorithmnotes

• 14.07. Robot Navigation ctd., Competitive Bidding, Exercise: Cows & Robotsnotes

5. Online Algorithms

• 16.07. The Paging problem notes

• 21.07. Renting Skies and Buying a Bahn Card notes

6. Probabilistic Method

• 23.07. Lovasz Local Lemmanotes