Differences between revisions 8 and 54 (spanning 46 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: 19.05.14) of the script can be viewed here.

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

*****IMPORTANT: if you plan to take the exam, please send me an email until 23.05. (the words exam and randomized algorithms should appear in the subject)*****

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 notes example code
19.05. Fingerprinting and Further Hashing Applications, Introduction to Samplingnotes
21.05. VC-dimension of Set Systems
26.05.
28.05. no lecture
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. test exam
30.07. test exam

-  ⇤ ← Revision 8 as of 2014-04-01 14:14:18 → 
  Size: 706
  Editor: Sabine Storandt
  Comment:
+   ← Revision 54 as of 2014-05-19 10:57:26 → ⇥
  Size: 2987
  Editor: adpult
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 3:
-The course is given by [[http://ad.informatik.uni-freiburg.de/staff/storandt|Dr. Sabine Storandt]]. It takes place every Monday and Wednesday from 10:15am until 11:45am in the Hörsaal HS036 in building 101. Exercises (E) will be bi-weekly, starting at 30.04.2014.
+The course is given by [[http://ad.informatik.uni-freiburg.de/staff/storandt|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.
 Line 5:
-.04.
+'''Topics'''
 Line 7:
-.04. (E)
+- Las Vegas & Monte Carlo Algorithms
 Line 9:
-.05.
+- Applications for Randomized Algorithms and Data Structures
 Line 11:
-.05.
+- Improving Deterministic Bounds via Randomization
 Line 13:
-.05.
+- Randomization in Games and AI
 Line 15:
-.05. (E)
+- Randomized Online Algorithms
 Line 17:
-.05.
+- Probabilistic Method
 Line 19:
-.05.
-Line 21:
+Line 20:
-.05.
-Line 23:
+Line 21:
-.05. (E) -> replacement lecturer
+'''Script'''
-Line 25:
+Line 23:
-.06.
+The complete script of the lecture (including further references) will be made available in the course svn repository.
-Line 27:
+Line 25:
-.06.
+The current version (last change: 19.05.14) of the script can be viewed [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/script.pdf|here.]]
-Line 29:
+Line 27:
-Pfingstpause
+(The list of contents may still change during the course of the lecture.)
-Line 31:
+Line 29:
-.06.
+{{{#!html
<span style="color:red">*****IMPORTANT: if you plan to take the exam, please send me an email until 23.05. (the words exam and randomized algorithms should appear in the subject)*****</span>
}}}
 Line 33:
-.06. (E)
-Line 35:
+Line 34:
-.06.
-Line 37:
+Line 35:
-.06.
-Line 39:
+Line 36:
-.06.
-Line 41:
+Line 37:
-.07. (E)
-Line 43:
+Line 38:
-.07.
+'''Dates'''
-Line 45:
+Line 40:
-.07.

14.07.

16.07. (E)

21.07.

23.07.

28.07.

30.07. (E)
+ * 28.04. ''Introduction & Basic Stochastics'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture1.pdf|notes]]
 * 30.04. ''Las Vegas and Monte Carlo Algorithms: Analysis and Concentration Bounds, LV & MC for Max 3-SAT'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture2.pdf|notes]]
 * 05.05. ''k-Select, Approximative Median and Quick-Sort, Sorting Lower Bound'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture3.pdf|notes]]
 * 07.05. ''Sorting Lower Bounds continued, Deterministic & Randomized Skip-Lists''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture4.pdf|notes]]
 * 12.05. ''Universal Hashing''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture5.pdf|notes]]
 * 14.05. ''Exercise. Focus: Deterministic & Randomized Sorting'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture6.pdf|notes]][[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Code/sort|example code]]
 * 19.05. ''Fingerprinting and Further Hashing Applications, Introduction to Sampling''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture7.pdf|notes]]
 * 21.05. ''VC-dimension of Set Systems''
 * 26.05.
 * 28.05. ''no lecture'' :(
 * 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. ''test exam''
 * 30.07. ''test exam''