Randomized Algorithms (semester 2011A)

Weizmann Institute of Science

[Course description] [Lectures] [Assignments] [Related material]

Course description:

Instructors: Robert Krauthgamer and Moni Naor

When and where: Sunday 4-6pm, Ziskind Lecture Rm 1

FGS code: 20114151

Syllabus: Algorithms that are randomized, i.e. use coin tosses during their execution, are central in many computational scenarios, and have become a key tool in the design and analysis of new algorithms. The course will cover the development and use of such probabilistic techniques, including some of the following topics: Concentration results; Simulating randomness, in particular limited independence; Load balancing; Routing algorithms; Randomized rounding; Sampling and sublinear algorithms; Algorithms in the data stream model; Communication protocols and the sketching model

Prerequisites: Students are expected to be familiar with algorithms, complexity theory,  probability theory, and linear algebra, at an undergraduate level.

Evaluation (grade): Homework (minimum 70% successful submission) and a final exam.

Lectures:

1. Oct. 31 (RK). Randomized quicksort. Analysis in terms of expectation and WHP. Markov’s inequality and Chernoff-Hoeffding concentration bounds.

• Additional reading: [MR, chapters 1 and 4.1], [DP, chapters 3.3.3 and 1.6]

2. Nov. 7 (RK). The sketching model, alternative view as a simultaneous communication protocol, algorithm for testing equality, algorithm for estimating L_1 (and Hamming) distance.
3. Nov. 14 (MN).  Why Randomized Algorithms?, The importance of concentration, and Streaming Algorithms and Pair-wise independence

• Notes for Lecture 3 

4. Nov. 21 (MN).  Authentication, Multi Set comparison and memory checking, Schwartz-Zippel and matching

• Notes for Lecture 4 

5. Nov. 28 (RK).  Approximate Nearest Neighbor Search algorithms for Hamming distance and L_1, using either sketching protocols or Locality Sensitive Hashing (LSH)

• Additional reading:  Indyk-Motwani (1998) and Kushilevitz-Ostrosvky-Rabani (2000).

6. Dec. 5: no class (Hannukka)
7. Dec. 12 (RK). Estimating a sum by Subsampling and by Precsision Sampling.

• Additional reading: Andoni-Krauthgamer-Onak (2010), sections 1.2 and 2.

8. Dec. 19 (RK). Data stream algorithms: L_2 norm (and F_2 frequency moment), and L_1 point queries and heavy hitters.

• Additional reading: course notes (by Indyk), lectures 2 and 4.

9. Dec. 26 (RK). Estimating the L_1 norm of a data stream via precision sampling.

• Additional reading: Andoni-Krauthgamer-Onak (2010), section 3.

10. Jan. 2. (MN) Balls and Bins, Mitzenmacher-Upfal Chapter 5, Stable Matching analysis Motwani-Raghavan Chapter 3.5 and 3.6. Alivn Roth’s retrospective paper on Gale and Shapley’s work

• Notes for lecture 10

11. Jan. 9. Elchanan Mossel, extraction of coins and Omer Tamuz, Cake Cutting. Ariel Proccia’s blog entry on the subject.
12.  Jan. 16. (MN) Power of two choice, Mitzenmacher-Upfal Chapter 14, Mittzemcaher, Richa and Sitaraman, Anupam Gupta’s notes, Berthold Voecking’s presentation
13. Jan. 23. (MN) Finish two-choice. Cuckoo Hashing: slides, original paper by Pagh and Rodler, paper on deamortized cuckoo hashing. Approximate Set Membership - Bloom Filters survey
14. Jan. 30. No Class
15.  Feb. 6. (MN) Markov Chains and Random Walks. Mitzenmacher-Upfal  Chapter 7 and Motwani-Raghavan Chapter 6. Algorithms for SAT: Schoening’s paper, Its derandomization, the PPSZ paper. Slides by Uri Feige on Random Walks. Generating random spanning trees: Broder and Aldous, Wilson’s algorithm.

Exam: will take place on Feb. 23, at 10am, Ziskind 1.

Here are some review questions for practice purposes (posted Feb. 19).

Here is the final exam itself.

Assignments:

(Should be turned in within two weeks)

• Problem set 1 (posted Nov. 1)
• Problem set 2 (posted Nov. 8)
• Problem set 3 (posted Nov. 29, due Dec. 12)
• Problem set 4 (posted Dec. 20, due Jan. 2)
• Problem set 5 (Due Feb 6th)

Some review questions for practice purposes are available above.

Related material:

Courses at other universities (many with lecture notes):

• Randomized Algorithms and Probabilistic Analysis by James R. Lee at UW (2008)
• Randomized Algorithms by Anupam Gupta and Shuchi Chawla at CMU (2004)
• Randomized Algorithms by David Karger at MIT (2007)
• Randomized Algorithms by Avrim Blum at CMU (1997)

Relevant textbooks:

• [MR] Randomized Algorithms by Motwani and Raghavan.
• [MU] Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal.
• [DP] Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi.

Useful references:

• The Probabilistic Method by Alon and Spencer (3rd Edition).

• Concentration by Colin McDiarmid. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46.

• Probability and Random Processes (2nd ed.) by Grimmett and Stirzaker.