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 some further references) is available in the course svn repository.
The final version (last change: 28.08.14) of the script can be viewed here.
Exam
The oral exam takes place at 26.08.2014.
Here is a list of example questions that are likely to be asked in the exam.
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.
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
6. Probabilistic Method
23.07. Lovasz Local Lemmanotes