#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: 29.07.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. '''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]]