#acl Sabine Storandt:read,write Axel Lehmann:read,write All:read = Randomized Algorithms (summer term 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 '''Script''' The complete script of the lecture (including some further references) is available in the course svn repository. The final version (last change: 20.08.14) of the script can be viewed [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/script.pdf|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. @12.08.14: S.60 With the optimal cost being equal to αM , the resulting ratio is 1 + 2/α ====> the resulting ratio is 1 + 1/(2α) @16.08.14: S.49 the sum of 2^{i+1}^ from i=1 to j+1 is not 2(2 ^ {j+2}^ -1) but 2(2 ^ {j+2}^ -2), and in the same flavour the sum of 2^{i+1}^ from i=1 to j is not 2(2 ^ {j+1}^ -1) but 2(2 ^ {j+1}^ -2) @19.08.14: S.13 |A1 | ≥ k instead of |A1 | > k @19.08.14: S.22 Lemma 2.12 |U | ≥ (n − 1) · m + 1 instead of |U | ≥ (n − 1) (m + 1) @20.08.14: S.39 P(n) >= (1 - 2/n) * P(n - 1) anstatt P(n) <= (1 - 2/n) * P(n - 1) @20.08.14: S.41 FastCut has to reduce the number of nodes down to (n+1)\sqrt(2) to make the success probability larger than 1/2, also the screw up probabilty missed the '1-' term at the beginning @20.08.14: S.49 The sum in Lemma 4.1 is n^2+2n, not n^2. '''Exam''' The oral exam takes place at 26.08.2014. [[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. '''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'' [[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]]