#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: 28.08.14) of the script can be viewed [[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/script.pdf|here.]] '''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]]