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:
http://www.wisdom.weizmann.ac.il/~robi/teaching/2011a-RandomizedAlgorithms
Announcements
The exam will take place at FGS room B .
Lectures
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]
2012-11-11, Robi: The second moment, more occupancy problems,
data-stream algorithms for L_2-norm and for point queries.
[lecture notes #2 ]
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.
2012-11-25, Moni: Bloom filter, maximal independent set,
closest points.
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)
2012-12-16, Moni: Cuckoo Hashing, construction of k-wise
independent hash functions, random codes [slides ]
2012-12-23, Robi: Global Minimum Cuts and Edge Sparsification
[lecture notes #7 ]
2012-12-30, Robi: Edge Sparsification (cont'd) and Distance
Oracles [lecture notes #8 ]
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.
2013-01-13, Moni: Markov Chains: Random Walks, Mixing Times
and Coupling
2013-01-20, Robi: Importance Sampling, and the Local Lemma [lecture notes #11 ]
2013-01-27, Robi: Nearest Neighbor Searching (NNS) in High
Dimension [lecture notes #12 ]
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].
Assignments
(Should be turned in within two weeks)
Reading material
Relevant textbooks:
Similar courses (many with lecture notes):
Useful references: