Differences between revisions 5 and 42 (spanning 37 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 further references) will be made available in the course svn repository.

The current version (last change: 12.05.14) of the script can be viewed here.

(The list of contents may still change during the course of the lecture.)

Dates

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
05.05. k-Select, Approximative Median and Quick-Sort, Deterministic Sorting Lower Bound notes
07.05. Sorting Lower Bounds continued, Deterministic & Randomized Skip-Listsnotes
12.05. Hashing notes
14.05. Exercise. Focus: Deterministic & Randomized Sorting
19.05.
21.05.
26.05.
28.05. no lecture
02.06.
04.06.
16.06.
18.06.
23.06.
25.06.
30.06.
02.07.
07.07.
09.07.
14.07.
16.07.
21.07.
23.07.
28.07. test exam
30.07. test exam

-  ⇤ ← Revision 5 as of 2014-04-01 14:12:45 → 
  Size: 13269
  Editor: Sabine Storandt
  Comment:
+   ← Revision 42 as of 2014-05-12 14:53:59 → ⇥
  Size: 2295
  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 03-26 in building 51.
-Line 4:
+Line 5:
-== Important Links ==
 * 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.
+'''Topics'''
-Line 11:
+Line 7:
-== Lecture Slides, Video Recordings, Exercise Sheets, and Code ==
 * 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]].
+- 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: 12.05.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.)



'''Dates'''

 * 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]]
 * 05.05. ''k-Select, Approximative Median and Quick-Sort, Deterministic 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. ''Hashing ''[[https://daphne.informatik.uni-freiburg.de/svn-public/RandomizedAlgorithmsSS2014/public/lectures/Lecture5.pdf|notes]]
 * 14.05. ''Exercise. Focus: Deterministic & Randomized Sorting''
 * 19.05.
 * 21.05.
 * 26.05.
 * 28.05. no lecture :(
 * 02.06.
 * 04.06.
 * 16.06.
 * 18.06. 
 * 23.06.
 * 25.06.
 * 30.06.
 * 02.07. 
 * 07.07.
 * 09.07.
 * 14.07.
 * 16.07. 
 * 21.07.
 * 23.07.
 * 28.07. test exam
 * 30.07. test exam