Randomized algorithms, Fall 2004

[Course description] [Schedule] [Sign up] [Literature] [Prerequisites] [Course format] [Examination] [Lecturers]

News

Exercises on November 23:

MU section 6.10, exercises 2, 4, 5, and 16. In 16, the coloring should use two colors.

Course description

There are many problems that can be solved more efficiently and by a simpler algorithm, when we have free access to a source of random bits, compared to when we have no such access.

The course will contain basic tools from probability theory and probabilistic analysis: Sums of indicator variables; Game theoretic techniques and Yao's lower bound technique; Tail inequalities in particular Chernoff bounds;

There will also be some concrete examples of randomized algorithms and their analysis in a representative selection of models and application areas.

The content of the last three lectures is not yet decided, but we will try to find some intersting newer results to talk about.

See the schedule below for more details.

Schedule

The schedule is preliminary. We will discuss both content, form and times during the course.

Date Time Subject Literature Exercises / hand-ins Place
Sept. 7 11-16 Introduction to randomized algorithms. (GSF) MR 1-1.3, 1.5, 2.1, 10.2   4A 22
Sept. 17 13-15 Exercise session on last week's material.(RP+AP) September 17/21 3A 18
Sept. 21 11-16 Randomized algorithms: Proving lower bounds, Derandomization, Chernoff bounds and randomized rounding. (GSF) MR 2.2-2.3, 3.2, 3.4, 4.1-4.3.   4A 22
Sept. 28 13-15 Exercise session on last week's material.(RP+AP) Sept. 28/Oct. 5 4A 22
Oct. 5 11-16 Algebric techniques in randomization, Competitive analysis of on-line algorithms. (GSF) MR 7-7.6, 13-13.3   4A 22
Oct. 12 13-15 Exercise session on last week's material.(RP+AP) MR 7.2, 7.10, 7.12, 13.6, 13.10 4A 22
Oct. 26 10-12 + 13-14 Balls and Bins (AP) MU 5.1, 5.2, 5.5 4A 22
Nov. 2 10-12 + 13-14 Lecture: Random graphs and expanders, with applications (RP) MU 5.6, BMRS00, section 3.2, BHK04, section 6 Exercises: 4, 11, 22, 24 from MU chapter 5 4A 22
Nov. 9 10-12 + 13-14 Lecture: The probabilistic method, part I (AP) OP02 sect. 2, MU 6.1, 6.2, 6.3, 6.4, H03 See "news" above 4A 22
Nov. 16 10-12 + 13-14 Lecture: The probabilistic method, part II (AP) MU 6.5-6.8   4A 22
Nov. 23 10-12 + 13-14 Lecture: Hashing, episode I: Post-universal hashing (RP) M98, P04 P01 problems 1 and 4. 4A 22
Nov. 30 10-12 + 13-14 Lecture: Hashing, episode II: Open adressing (RP)   4A 22
Literature:

Sign up for the course

To sign up for the course, please send an e-mail to annao@itu.dk before the first lecture.

Literature

The book Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan will be primary literature in the course. There will probably be some supplemantary material, especially for the three last lectures.

Prerequisites

A couple of algorithm courses will be helpful as well as some knowledge of basic probability theory (there is an appendix in the book to study before the course on basic probability theory, if necessary). Please contact annao@itu.dk if you have doubts about your background.

Course format

Teaching consists of lectures and exercises in English. Every other week there will be lectures from 11 to about 16. There will be exercises handed out every lecture and the following week we will have an exercise session from 13 to about 15. You are expected to work on the material before the exercise session. Those of who come from another university may choose to arrange your own exersice sessions to avoid too much travel. There will be mandatory hand-ins, see below.

Mandatory hand-ins

There will be mandatory hand-ins, which will be used as the only form of examination. There will be 4-5 hand-ins. Hand-ins may be in Danish, Swedish or English.

Examination

Madatory hand-ins is the only form of examination.

Lecturers

Gudmund Skovbjerg Frandsen
Office: Århus University
Phone: +45 8942 5772
Email: gudmund@daimi.au.dk
 Rasmus Pagh
Office: 3C.07, ITU
Phone: +45 7218 5284
Email: pagh@itu.dk
 Anna Östlin Pagh
Office: 3C.11, ITU
Phone: +45 7218 5290
Email: annao@itu.dk