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

Please report any kind of mistakes (grammar, spelling, content) via email. Content errors corrected after 29.07.2014 will be listed on this website for easy adaption of printed scripts.

@12.08.14: S.60 With the optimal cost being equal to αM , the resulting ratio is 1 + 2/α ====> the resulting ratio is 1 + 1/(2α)

@16.08.14: S.49 the sum of 2^{i+1} from i=1 to j+1 is not 2(2 ^{j+2} -1) but 2(2 ^{j+2} -2), and in the same flavour the sum of 2^{i+1} from i=1 to j is not 2(2 ^{j+1} -1) but 2(2 ^{j+1} -2)

@19.08.14: S.13 |A1 | ≥ k instead of |A1 | > k

@19.08.14: S.22 Lemma 2.12 |U | ≥ (n − 1) · m + 1 instead of |U | ≥ (n − 1) (m + 1)

@20.08.14: S.39 P(n) >= (1 - 2/n) * P(n - 1) anstatt P(n) <= (1 - 2/n) * P(n - 1)

@20.08.14: S.41 FastCut has to reduce the number of nodes down to (n+1)\sqrt(2) to make the success probability larger than 1/2, also the screw up probabilty missed the '1-' term at the beginning

@20.08.14: S.49 The sum in Lemma 4.1 is n²+2n, not n².

@22.08.14: S.55 W_i \leq W and W_i \geq W makes no sense of course, just W_i \geq W is correct, the other term needs to be deleted

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

• 16.07. The Paging problem notes

• 21.07. Renting Skies and Buying a Bahn Card notes

6. Probabilistic Method

• 23.07. Lovasz Local Lemmanotes