Differences between revisions 8 and 128 (spanning 120 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 some further references) is available in the course svn repository.

The final version (last change: 28.08.14) of the script can be viewed here.

Exam

The oral exam takes place at 26.08.2014.

Here is a list of example questions that are likely to be asked in the exam.

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.

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
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. 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)notes example code connected components example 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

16.07. The Paging problem notes
21.07. Renting Skies and Buying a Bahn Card notes

6. Probabilistic Method

23.07. Lovasz Local Lemmanotes

-  ⇤ ← Revision 8 as of 2014-04-01 14:14:18 → 
  Size: 706
  Editor: Sabine Storandt
  Comment:
+   ← Revision 128 as of 2014-08-28 08:35:01 → ⇥
  Size: 6331
  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 some further references) is available in the course svn repository.
-Line 27:
+Line 25:
-.06.
+The final version (last change: 28.08.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
+'''Exam'''
-Line 31:
+Line 29:
-.06.
+The oral exam takes place at 26.08.2014.
-Line 33:
+Line 31:
-.06. (E)
+[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/questions.pdf|Here]] is a list of example questions that are likely to be asked in the exam.
-Line 35:
+Line 33:
-.06.
-Line 37:
+Line 34:
-.06.
+'''Question Time'''
-Line 39:
+Line 36:
-.06.
+==> 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.
-Line 41:
+Line 38:
-.07. (E)
-Line 43:
+Line 39:
-.07.
-Line 45:
+Line 40:
-.07.
+'''Dates'''
-Line 47:
+Line 42:
-.07.

16.07. (E)

21.07.

23.07.

28.07.

30.07. (E)
+. 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]]
 * 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. Getting 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)''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture16.pdf|notes]][[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Code/cc|example code connected components]][[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Code/mincut|example code min cut]]
4. Randomization in AI
 * 02.07. ''Exercise (Min Cut ctd. and Long Path) + The Cow Path Problem'' [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture17.pdf|notes]]
 * 07.07. ''Robot Navigation in Unknown Terrain: Deterministic Algorithms''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture18.pdf|notes]]
 * 09.07. ''Robot Navigation in Unknown Terrain: Randomized Algorithm''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture19.pdf|notes]]
 * 14.07. ''Robot Navigation ctd., Competitive Bidding, Exercise: Cows & Robots''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture20.pdf|notes]]
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]]