Randomized Algorithms (semester 2013A)

Weizmann Institute of Science

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

Course description

Instructors: Robert Krauthgamer and Moni Naor

Grader: Gilad.Tsur (at weizmann.ac.il)

When and where: Sundays, 2-5pm, Ziskind Lecture Room 1

First class: November 4, 2012

FGS code: 20134151

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 17, 2013 (at 10am).
Here is the final exam itself.

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

Previous offering:



  1. 2012-11-04, Robi: Randomized quicksort. Markov’s inequality and Chernoff-Hoeffding concentration bounds. Some occupancy problems. [lecture notes #1]
  2. 2012-11-11, Robi: The second moment, more occupancy problems, data-stream algorithms for L_2-norm and for point queries. [lecture notes #2]
  3. 2012-11-18, Robi: Proof of Hoeffding's bound, heavy hitters via point queries, and sketching algorithms. [lecture notes #3
  4. 2012-11-25, Moni: Bloom filter, maximal independent set, closest points.
  5. 2012-12-02, Moni: Martingales, Closest Pairs, Hash Tables, Existential Proofs and Codes. [lecture notes #5

    2012-12-09: no class (HANNUKKAH)

  6. 2012-12-16, Moni: Cuckoo Hashing, construction of k-wise independent hash functions, random codes [slides]
  7. 2012-12-23, Robi: Global Minimum Cuts and Edge Sparsification [lecture notes #7]
  8. 2012-12-30, Robi: Edge Sparsification (cont'd) and Distance Oracles [lecture notes #8]
  9. 2013-01-06, Moni: The power of two choices and Markov chains
  10. 2013-01-13, Moni: Markov Chains: Random Walks, Mixing Times and  Coupling
  11. 2013-01-20, Robi: Importance Sampling, and the Local Lemma [lecture notes #11]
  12. 2013-01-27, Robi: Nearest Neighbor Searching (NNS) in High Dimension [lecture notes #12]
  13. 2013-02-07, Moni: Minmax theorem and its applications to lower bounds in randomized algorithms (Yao's principle) [MR, Chapter 2.1-2.2], competitive analysis of online algorithms [MR, Chapter 13], analysis of stable matching [MR, Chapters 3.5-3.6].


(Should be turned in within two weeks)

Reading material

Relevant textbooks:

Similar courses (many with lecture notes):

Useful references: