|
Size: 863
Comment:
|
Size: 3209
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | 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. '''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 |
| Line 9: | Line 25: |
| The current version (last change: 21.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.) {{{#!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 11: | Line 40: |
| * 28.04. Introduction & Basic Stochastics * 30.04. * 05.05. * 07.05. * 12.05. * 14.05. * 19.05. * 21.05. * 26.05. * 28.05. |
* 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 & Epsilon-Nets'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture8.pdf|notes]] * 26.05. ''Exercise + Good Random Samples for Systems with Small VC-dimension and Epsilon-Nets'' * 28.05. ''no lecture'' :( |
| Line 35: | Line 64: |
| * 28.07. * 30.07. (E) |
* 28.07. ''test exam'' * 30.07. ''test exam'' |
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: 21.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 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
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