Differences between revisions 20 and 33 (spanning 13 versions)

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

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

Dates

28.04. Introduction & Basic Stochastics
30.04. Las Vegas and Monte Carlo Algorithms: Analysis and Concentration Bounds, LV & MC for Max 3-SAT
05.05. k-Select, Approximative Median and Quick-Sort, Deterministic Sorting Lower Bound
07.05. Sorting Lower Bounds continued, Deterministic & Randomized Skip-Lists
12.05.
14.05. Exercise: Deterministic & Randomized Sorting in C++
19.05.
21.05.
26.05.
28.05.
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.
30.07.

-  ⇤ ← Revision 20 as of 2014-04-28 11:09:06 → 
  Size: 1224
  Editor: adpult
  Comment:
+   ← Revision 33 as of 2014-05-05 11:36:14 → ⇥
  Size: 1655
  Editor: adpult
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 19:
-Line 23:
+Line 25:
-The current version of the script can be viewed under: https://daphne.informatik.uni-freiburg.de/svn/RandomizedAlgorithmsSS2014/public/script.pdf
+The current version (last change: 05.05.14) of the script can be viewed [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/script.pdf|here.]]

(The list of contents may still change during the course of the lecture.)
-Line 28:
+Line 34:
- * 30.04. 
 * 05.05.
 * 07.05.
+ * 30.04. ''Las Vegas and Monte Carlo Algorithms: Analysis and Concentration Bounds, LV & MC for Max 3-SAT''
 * 05.05. ''k-Select, Approximative Median and Quick-Sort, Deterministic Sorting Lower Bound''
 * 07.05. ''Sorting Lower Bounds continued, Deterministic & Randomized Skip-Lists''
-Line 32:
+Line 38:
- * 14.05.
+ * 14.05. ''Exercise: Deterministic & Randomized Sorting in C++''