Differences between revisions 13 and 84 (spanning 71 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: 28.06.14) of the script can be viewed here.

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

Exam

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.

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 notes example 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
28.05. no lecture
02.06. Good Hitting Set Approximations notes
04.06. Route Planning and Epsilon-Nets notes
16.06. Exercise. Focus: Hitting Sets for Road Networksnotes example code

3. Going 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)
02.07.
07.07.
09.07.
14.07.
16.07.
21.07.
23.07.
28.07. test exam
30.07. test exam

-  ⇤ ← Revision 13 as of 2014-04-23 12:59:14 → 
  Size: 1122
  Editor: adpult
  Comment:
+   ← Revision 84 as of 2014-06-30 07:38:56 → ⇥
  Size: 4486
  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 8:
-Line 9:
+Line 10:
-Line 10:
+Line 12:
-Line 11:
+Line 14:
-Line 12:
+Line 16:
-Line 13:
+Line 18:
-Line 18:
+Line 25:
+The current version (last change: 28.06.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.)


'''Exam'''

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.
-Line 20:
+Line 38:
- * 28.04. Introduction & Basic Stochastics
 * 30.04. 
 * 05.05.
 * 07.05.
 * 12.05.
 * 14.05. 
 * 19.05.
 * 21.05.
 * 26.05.
 * 28.05. 
 * 02.06.
 * 04.06.
 * 16.06.
 * 18.06. 
 * 23.06.
 * 25.06.
 * 30.06.
+. Preliminaries
 * 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]]
2. Randomized Algorithms and Data Structures
 * 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'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture9.pdf|notes]]
 * 28.05. ''no lecture'' :(
 * 02.06. ''Good Hitting Set Approximations'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture10.pdf|notes]]
 * 04.06. ''Route Planning and Epsilon-Nets'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture11.pdf|notes]]
 * 16.06. ''Exercise. Focus: Hitting Sets for Road Networks''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture12.pdf|notes]][[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Code/hit|example code]]
3. Going Beyond Deterministic Bounds via Randomization
 * 18.06. ''The Closest Pair problem''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture13.pdf|notes]]
 * 23.06. ''The Min Cut problem''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture14.pdf|notes]]
 * 25.06.  ''Sublinear Algorithms''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture15.pdf|notes]]
 * 30.06. ''Long Path problems + Exercise (Min Cut and Connected Components)''
-Line 44:
+Line 65:
- * 28.07.
 * 30.07. (E)
+ * 28.07. ''test exam''
 * 30.07. ''test exam''