Teaching

Seminar Randomized Algorithms (WS 10/11)

Tobias Friedrich and Thomas Sauerwald

Time:

Tuesday (usually 10:15-11:45)

First meeting:

26.10.2010 (2nd week of the semester)

Room:

024 in the MPI building (E1 4)

Prerequisites:

Basic knowledge of algorithms and probability theory.

Registration:

Please register here for the course. You can unregister here. Within a few weeks after the semester starts, you will of course also have to subcribe to the HISPOS system of the university.

Content:

For many applications a randomized algorithm is the simplest and/or fastest algorithm available. Randomized methods are a very powerful tool to find good algorithms, both from the theoretical viewpoint and the application one. In the seminar, the students will present some particularly interesting topics regarding randomized algorithms and their analyses.

Credits:

You earn the usual 7 LPs for a seminar if you complete the following tasks. You'll be given an research article about a particular topic on randomized algorithms. You carefully read it and give a talk (40 min) on the content of the article and write a short summary (about 5 pages).

Schedule:

Date	Lecturer	Topic	Reference
26.10. 10:15-11:45	Tobias Friedrich Thomas Sauerwald	Assignment of topics
23.11. 10:15-12:00	Yash Raj Shrestha Manish Kumar Narang	Random walks	1 2
30.11. 10:30-12:00	Lena Kinzel	Random walks	5
14.12. 10:15-12:00	Vijay Ingalalli Goran Doychev	Broadcasting	6 7
11.01. 18:15-20:00	Nils Jasper	Broadcasting	4
18.01. 10:15-12:00	Ahed Alahmar Daniel Wand	Broadcasting Hashing	12 20
01.02. 10:15-12:00	Jan Balzer Wenkai Dai	Load balancing	15 16

References:

Standard textbooks on randomized algorithms are Motwani and Raghavan and Mitzenmacher and Upfal. For random walks a nice online reference is Levin, Peres, and Wilmer.

Papers: