Randomized Algorithms (semester 2013A)

[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: http://www.wisdom.weizmann.ac.il/~robi/teaching/2011a-RandomizedAlgorithms

Announcements

• The exam will take place at FGS room B.

Lectures

1. 2012-11-04, Robi: Randomized quicksort. Markov’s inequality and Chernoff-Hoeffding concentration bounds. Some occupancy problems. [lecture notes #1]
   • Additional reading: [MR, chapters 1, 3.1 and 4.1], [DP, chapters 3.3.3 and 1.6]
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]
   • Additional reading: [MR, chapters 3.1, 3.2, 3.6], [MU, chapter 3.3], course notes (by Indyk) lectures 2 and 4; encyclopedia of database systems entry (by Cormode).
3. 2012-11-18, Robi: Proof of Hoeffding's bound, heavy hitters via point queries, and sketching algorithms. [lecture notes #3] 
• Additional reading: [DP, chapter 1.5], same as previous class.
4. 2012-11-25, Moni: Bloom filter, maximal independent set, closest points.
• Additional reading: bloom filter survey, lecture notes (by Roger Wattenhofer), Klienberg-Tardos's book chapter.
5. 2012-12-02, Moni: Martingales, Closest Pairs, Hash Tables, Existential Proofs and Codes. [lecture notes #5] 
   • Additional reading:
     
   • Noga Alon, Martin Dietzfelbinger, Peter B. Miltersen, Erez Petrank, and Gabor Tardos, Linear Hashing, Journal of the ACM, Vol. 46(5), 1999.
   • J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. Syst. Sci. 18 (1979) 143--154.
   • Eric Demaine, Lecture 10 in course 6.851: Advanced Data Structures (Spring'12) on Dictionaries.
   • Paul Erdos, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (4), 1947, pp. 292-–294.
   • Jon Kleinberg and Eva Tardos, Algorithm Design. Addison Wesley, 2006. Chapter 13.
     
   • Dick Lipton's blog, Rabin Flips a Coin, March 2009.
   • Rene Schoof, Four primality testing algorithms, arXiv 0801.3840. 

   2012-12-09: no class (HANNUKKAH)
   

6. 2012-12-16, Moni: Cuckoo Hashing, construction of k-wise independent hash functions, random codes [slides]
   • Additional reading:
   • The original Journal paper:  R. Pagh and F. F. Rodler, Cuckoo Hashing.
     
   • Patrascu and Thorup's work on The Power of Simple Tabulation Hashing.
     
   • Blogs on cuckoo hashing: by Mihai Patrascu: here; and by Michael Mitzenmacher: part1, part2, part3.
     
7. 2012-12-23, Robi: Global Minimum Cuts and Edge Sparsification [lecture notes #7]
   
   • Additional reading: [MR, chapters 1.1 and 10.2], [MU, chapter 1.4], the Benczur-Karger paper.
8. 2012-12-30, Robi: Edge Sparsification (cont'd) and Distance Oracles [lecture notes #8]
   
   • Additional reading: the Benczur-Karger paper, the Thorup-Zwick paper.
     
9. 2013-01-06, Moni: The power of two choices and Markov chains
   
   • Additional reading: [MU, chapters 14 and 7], a survey on two choices by Mitzenmacher, Richa and Sitaraman.
     
10. 2013-01-13, Moni: Markov Chains: Random Walks, Mixing Times and  Coupling
    
    • Additional reading: [MU, chapters 7 and 11]; Manuscript on Mixing time by Levin, Peres and Wilmer; Analysis of the Thorp Shuffle by Morris, Rogaway and Stegers.
      
11. 2013-01-20, Robi: Importance Sampling, and the Local Lemma [lecture notes #11]
    • Additional reading for importance sampling: [MR, chapters 11.2]; class notes by Amin Saberi.
    • Additional reading for LLL: class notes by Joel Spencer, and class notes by Uri Feige; blog post by Terry Tao.
      
12. 2013-01-27, Robi: Nearest Neighbor Searching (NNS) in High Dimension [lecture notes #12]
    
    • Additional reading: the Indyk-Motwani paper, the Kushilevitz-Ostrovsky-Rabani paper.
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].
    
    • Additional reading: Shahar Dobzinski's note on using the principle for deriving a lower bound, Alvin Roth’s retrospective paper on Gale and Shapley’s work.
      

Assignments

• problem set 1 (posted Nov. 5, concentration bounds)
• problem set 2 (posted Nov. 20)
• problem set 3 (posted Dec. 6, due Dec. 23)
• problem set 4 (posted Dec. 31)
• problem set 5 (posted Jan. 28, due Feb. 13)
  

Reading material

Relevant textbooks:

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

Similar courses (many with lecture notes):

• Randomized Algorithms by Sariel Har-Peled at UIUC (2010)
• 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)

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.