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:
- 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]
- 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.
- Nov. 14 (MN). Why Randomized Algorithms?, The importance of concentration, and Streaming Algorithms and Pair-wise independence
- Nov. 21 (MN). Authentication, Multi Set comparison and memory checking, Schwartz-Zippel and matching
- Nov. 28 (RK). Approximate Nearest Neighbor Search algorithms for Hamming distance and L_1, using either sketching protocols or Locality Sensitive Hashing (LSH)
- Dec. 5: no class (Hannukka)
- Dec. 12 (RK). Estimating a sum by Subsampling and by Precsision Sampling.
- Dec. 19 (RK). Data stream algorithms: L_2 norm (and F_2 frequency moment), and L_1 point queries and heavy hitters.
- Dec. 26 (RK). Estimating the L_1 norm of a data stream via precision sampling.
- 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
- Jan. 9. Elchanan Mossel, extraction of coins and Omer Tamuz, Cake Cutting. Ariel Proccia’s blog entry on the subject.
- Jan. 16. (MN) Power of two choice, Mitzenmacher-Upfal Chapter 14, Mittzemcaher, Richa and Sitaraman, Anupam Gupta’s notes, Berthold Voecking’s presentation
- 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
- Jan. 30. No Class
- 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)
Some review questions for practice purposes are available above.
Related material:
Courses at other universities (many with lecture notes):
Relevant textbooks:
Useful references: