Randomized Algorithms (semester 2015A)

Weizmann Institute of Science

[Course description] [Announcements] [Lectures] [Assignments] [Reading material]

Course description

Instructors: Robert Krauthgamer and Moni Naor

Grader: Lior.Kamma (at weizmann.ac.il)

When and where: Tuesdays, 14:15-17:00, Ziskind Lecture Room 1

First class: November 4, 2014

FGS code: 20154371

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 Theoretical Computer Science and in application areas. 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.

Exam: February 24, 2015 (at 10am, Ziskind #1).
Here is the final exam itself.

Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2015a-RandomizedAlgorithms

Previous offerings:




  1. 2014-11-04, Moni: Min Cut Algorithm, Closest Pairs, (Multi)-Set Equality [lecture notes #1]
  2. 2014-11-11, Moni: Maximal Independent Set, Analysis of Randomized Quicksort, Universal Hashing and Dictionaries, Concentration bounds- Chernoff [lecture notes #2]
  3. 2014-11-18, Moni: Random graphs, Azuma's inequality, and Bloom filters
  4. 2014-11-25, Moni: Hashing, Hamiltonicity of a random graph, Balls and Bins
  5. 2014-12-02, Robi: Edge Sparsification for Cuts [lecture notes #5]
  6. 2014-12-09, Robi: Distance Oracles and Distance Labeling [lecture notes #6
  7. 2014-12-16, Robi: Data streams, the AMS algorithm for l_2-norm, l_1-point queries, and heavy hitters [lecture notes #7]
  8. 2014-12-23, Robi: l_p-norm, p>2, of a data stream [lecture notes #8]
  9. 2014-12-30, Robi: Dimension Reduction in l_2, Sketching, and NNS in l_1 (with logarithmic query time) [lecture notes #9]
  10. 2015-01-06, Moni: Cuckoo Hashing
    2015-01-13: no class (due to ITCS)
  11. 2015-01-20: Moni: Oblivious RAM, Random walk algorithm for 2-SAT and 3-SAT
  12. 2015-01-27, Robi: Compressed Sensing and RIP matrices [lecture notes #12
  13. 2015-02-17, Robi: Communication Complexity Lower Bounds [lecture notes #13]


(Should be turned in within two weeks)

Reading material

Relevant textbooks:

Similar courses (many with lecture notes):

Useful references: