|
Size: 14161
Comment:
|
Size: 5939
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 2: | Line 2: |
| = 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. |
|
| Line 3: | Line 5: |
| = Randomized Algorithms (summer term 2014) = | '''Topics''' |
| Line 5: | Line 7: |
| The course is given by [[http://ad.informatik.uni-freiburg.de/staff/bast|Prof. Dr. Hannah Bast]] and assisted by [[http://ad.informatik.uni-freiburg.de/staff/buchhold|Björn Buchhold]]. It takes place every Tuesday from 4:15pm until 5:45pm in the Hörsaal HS036 in building 101. The first lecture is on Tuesday, October 22, 2013 and the last lecture is on Tuesday, February 11, 2014. There will be no lecture on Tuesday, December 24, 2013 and Tuesday, December 31, 2013 (christmas break) and on Tuesday, Januar 7, 2014. That is 14 lectures altogether. | - Las Vegas & Monte Carlo Algorithms |
| Line 7: | Line 9: |
| The tutors for this course are Stephanie Embgen (s.embgen@gmail.com), Jonas Sternisko (sternis@informatik.uni-freiburg.de) and Simon Skilevic (skilevis@informatik.uni-freiburg.de). The administrator of the supporting systems (Daphne, SVN, Forum, Jenkins) is [[http://ad.informatik.uni-freiburg.de/staff/lehmann|Axel Lehmann]]. | - Applications for Randomized Algorithms and Data Structures |
| Line 9: | Line 11: |
| == Important Links == | - Improving Deterministic Bounds via Randomization |
| Line 11: | Line 13: |
| * Here is the link to [[https://daphne.informatik.uni-freiburg.de/ws1314/InformationRetrieval/|Daphne]] (our course management system, login with your RZ user name and password). * Here is the link to the [[https://daphne.informatik.uni-freiburg.de/forum/viewforum.php?f=177|Forum]] (for announcements and questions, you are automatically a member when you have logged into Daphne). * Code style profiles for Eclipse: [[attachment:Eclipse Java Code Style Profile|Java]], [[attachment:Eclipse C++ Code Style Profile|C++]]. * Short introductions to SVN and Vim and the installation of gtest (for C++ only) can be found [[AlgoDatSS2013|here]] (in German). * The topics of this course will be similar to those of the course [[InformationRetrievalWS1213|Information Retrieval, WS 2012/2013]] from last year. Here is all about the [[InformationRetrievalWS1213/Exam|Exam]] from that course. |
- Randomization in Games and AI |
| Line 17: | Line 15: |
| == Lecture Slides, Video Recordings, Exercise Sheets, and Code == | - Randomized Online Algorithms |
| Line 19: | Line 17: |
| * Lecture 1, Tuesday, October 22, 2013 (Demo, Organizational, Inverted Index): [[http://youtu.be/42Fxjl1S8tE|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-1|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-01.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-01.pdf|Exercise Sheet 1]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-01/|Code from the lecture]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-01/InvertedIndex.TIP|Code design suggestion for ES1]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/people.tsv|Dataset for ES1 (961,327 abstracts about people)]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-01/|Solution for the exercise sheet]]. * Lecture 2, Tuesday, October 29, 2013 (Ranking, Vector Space Model, Evaluation): [[http://youtu.be/GNblyDPze04|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-2|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-02.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-02.pdf|Exercise Sheet 2]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-02/|TIP files for ES2]], [[InformationRetrievalWS1314/ResultsRanking|Table for your ranking results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-02/|Solution for the exercise sheet]]. * Lecture 3, Tuesday, November 5, 2013 (Efficient List Intersection): [[http://youtu.be/vexffAp6-xA|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-3|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-03.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-03.pdf|Exercise Sheet 3]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-03/|Code from the lecture]], [[InformationRetrievalWS1314/ResultsListIntersection|Table for your list intersection results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-03/|Solution for the exercise sheet]]. * Lecture 4, Tuesday, November 12, 2013 (Compression and Entropy): [[http://youtu.be/iuKEmtuIW0c|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-4|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-04.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-04.pdf|Exercise Sheet 4]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-04/|Complete code for VB-encoding (for both Java and C++)]], [[InformationRetrievalWS1314/ResultsCompression|Table for your compression results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-04/|Solution for the exercise sheet]]. * Lecture 5, Tuesday, November 19, 2013 (Fuzzy Search, Edit Distance, q-Gram Index): [[http://youtu.be/I_1t6wPgj8g|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-5|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-05.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-05.pdf|Exercise Sheet 5]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/entities-with-scores.txt|Dataset for ES5 (8.2M entity names from Freebase, with popularity scores)]],[[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-05/|Code for the PED + TIP files]], [[InformationRetrievalWS1314/ResultsErrorTolerantSearch|Table for your q-gram index results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-05/|Solution for the exercise sheet]]. * Lecture 6, Tuesday, November 26, 2013 (How to build a web application): [[http://youtu.be/CFRGTHdw_k8|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-6|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-06.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-06.pdf|Exercise Sheet 6]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-06/|Basic server code]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-06/|Solution for the exercise sheet]]. * Lecture 7, Tuesday, December 3, 2013 (Cookies, CORS, UTF-8): [[http://youtu.be/OQIWodfzICw|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-7|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-07.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-07.pdf|Exercise Sheet 7]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/entities-with-scores.iso-8859-1.txt|Dataset for ES7 (The entity names with scores from sheet 5 and 6 encoded in ISO-8859-1)]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-07/|Solution for the exercise sheet]]. * Lecture 8, Tuesday, December 10, 2013 (Synonyms, Latent Semantic Indexing): [[http://youtu.be/mB9slMuexOM|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-8|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-08.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-08.pdf|Exercise Sheet 8]], [[http://www.mpi-inf.mpg.de/~dfischer/alwis-1.1.0-full.exe|Alwis (Windows installer)]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-08/|Solution for the exercise sheet]]. * Lecture 9, Tuesday, December 17, 2013 (Clustering, K-Means): [[http://youtu.be/Ju2vFgiC_s4|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-9|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-09.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-09.pdf|Exercise Sheet 9]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-09/KmeansClustering.TIP|Invaluable implementation advice for this sheet]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/people-100K.txt|Dataset (100.000 abstracts about people)]], [[InformationRetrievalWS1314/ResultsClustering|Table for your clustering results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-09/|Solution for the exercise sheet]]. * Lecture 10, Tuesday, January 14, 2014 (Naive Bayes): [[http://youtu.be/7FCr3MJDQg0|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-10|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-10.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-10.pdf|Exercise Sheet 10]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-10/NaiveBayes.TIP|Implementation advice for this sheet]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/people.with-10-labels.txt|Dataset (50,562 abstracts about people, with class labels)]], [[InformationRetrievalWS1314/ResultsClassification|Table for your classification results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-10/|Solution for the exercise sheet]]. * Lecture 11, Tuesday, January 21, 2014 (Support Vector Machines): [[http://youtu.be/3jBGAsVmHak|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-11|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-11.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-11.pdf|Exercise Sheet 11]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-11/|Code from the lecture]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/people.actor+politician.txt|Dataset 1 (actors + politicians)]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/people.singer+songwriter.txt|Dataset 2 (singers + songwriters)]], [[InformationRetrievalWS1314/ResultsNaiveBayesMargin|Table for your margin results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-11/|Solution for the exercise sheet]]. * Lecture 12, Tuesday, January 28, 2014 (Ontologies, SPARLQ, Relation to SQL): [[http://youtu.be/Nw7qNQXN9O0|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-12|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-12.pdf|Slides]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-12.pdf|Exercise Sheet 12]], [[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/freebase-12M.tsv|12M facts from Freebase]], [[InformationRetrievalWS1314/ResultsSparql|Table for your SPARQL/SQL results]], [[https://daphne.informatik.uni-freiburg.de/svn/InformationRetrievalWS1314/solutions/sheet-12/|Solution for the exercise sheet]]. * Lecture 13, Tuesday, February 4, 2014 (Statistical Significance): [[http://youtu.be/oNqYtuUHpig|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-13|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-13.pdf|Slides (20 - 22 corrected twice)]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/exercises/sheet-13.pdf|Exercise Sheet 13]], [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/code/lecture-13/r-test.py|Code from the lecture]], [[InformationRetrievalWS1314/ResultsStatisticalSignificance|Table for your statistical significance results]]. * Lecture 14, Tuesday, February 11, 2014 (Evaluation, Exam, Work at our Chair): [[http://youtu.be/ahgdPO41bV0|Video Recording]] ([[http://ad-teaching.informatik.uni-freiburg.de/InformationRetrievalWS1314/get-video.php?file=lecture-14|Download]]), [[https://daphne.informatik.uni-freiburg.de/svn-public/InformationRetrievalWS1314/public/slides/lecture-14.pdf|Slides]], [[http://freebase-easy.cs.uni-freiburg.de|Freebase Easy Demo]], [[http://youtu.be/B19gOLYWy1Q|IceCite Demo]]. |
- 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: 08.07.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. '''Question Time''' Please use this Doodle [[http://doodle.com/z6zbuxw2ix23ym2k|Link]] to indicate if and when you would like to ask questions about the content of the lecture to prepare for the oral exam. '''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]] * 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. 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. * 23.07. * 28.07. ''test exam'' * 30.07. ''test exam'' |
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: 08.07.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.
Question Time
Please use this Doodle Link to indicate if and when you would like to ask questions about the content of the lecture to prepare for the oral exam.
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 notesexample 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 Networksnotesexample 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)notesexample code connected componentsexample 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.
- 23.07.
28.07. test exam
30.07. test exam