|
Size: 5689
Comment:
|
Size: 6434
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 23: | Line 23: |
| The complete script of the lecture (including further references) will be made available in the course svn repository. | The complete script of the lecture (including some further references) is available in the course svn repository. |
| Line 25: | Line 25: |
| The current version (last change: 08.07.14) of the script can be viewed [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/script.pdf|here.]] | The final version (last change: 29.07.14) of the script can be viewed [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/script.pdf|here.]] |
| Line 27: | Line 27: |
| (The list of contents may still change during the course of the lecture.) | 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. |
| Line 32: | Line 32: |
| The oral exam takes place at 26.08.2014. If you want to take the exam but the date is impossible for you, please write a mail. | The oral exam takes place at 26.08.2014. '''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. The final script as well as a catalogue of possible exam questions will be made available before. |
| Line 49: | Line 54: |
| * 28.05. ''no lecture'' :( | |
| Line 63: | Line 67: |
| 5. Online Algorithms * 16.07. ''The Paging problem'' * 21.07. * 23.07. * 28.07. ''test exam'' * 30.07. ''test exam'' |
5. Online Algorithms * 16.07. ''The Paging problem'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture21.pdf|notes]] * 21.07. ''Renting Skies and Buying a Bahn Card'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture22.pdf|notes]] 6. Probabilistic Method * 23.07. ''Lovasz Local Lemma''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture23.pdf|notes]] |
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: 29.07.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.
Exam
The oral exam takes place at 26.08.2014.
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. The final script as well as a catalogue of possible exam questions will be made available before.
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