Randomized Algorithms (semester 2019A)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures]
[Assignments] [Reading material]
Course description
Instructors: Robert
Krauthgamer and Moni Naor
Grader: Ohad.Trabelsi (at weizmann.ac.il)
When and where: Thursday 14:15-17:00, Ziskind Lecture Room
1
First class: Nov. 8, 2018
FGS code: 20194201
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.
Final: There will be a final assignment (take-home exam).
Here is the final exam itself.
Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2019a-RandomizedAlgorithms
Previous offerings:
http://www.wisdom.weizmann.ac.il/~robi/teaching/2017a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2015a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2013a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2011a-RandomizedAlgorithms
Announcements
- [posted 2019-02-07] the instructions for the final (take-home
exam) will be similar to this 2017
course.
- [posted 2019-01-04] Take-home
exam rescheduled: distributed Feb. 25, due within
3 days
- [posted 2018-12-28] Take-home schedule: distributed Feb. 10,
due within 3 days
- [posted 2018-12-24] Problem Set 2 was corrected (in Q.#2) with
extended due date
- [posted 2018-11-20] The class of Nov. 29 is moved (room
change) to Wolfson Hall
Lectures
- 2018-11-08, Moni: (Multi)-Set Equality, Closest Pair, Minimum
Cut.
Reading: lecture notes #1
- 2018-11-15, Robi: Random Walks on Graphs
Reading: lecture notes #2, see also
[MR, chapter 6]
Further reading: [Levin, Peres,
and Wilmer, chapter 9], [Doyle
and Snell, also as arXiv:math/0001057],
[Lyons and
Peres, chapter 2]
- 2018-11-22, Robi: Effective Resistance and an Algorithm for
2SAT
Reading: lecture notes #3, see also
[MU, chapter 7]
Further reading: [Feige,
slides on cover time]
- 2018-11-29, Ohad: 2-Universal Hash Families and Perfect
Hashing
Reading: [MU, chapter 13.3]
- 2018-12-06, Moni: Maximal Independent Set, Analysis of
Randomized Quicksort, Extractors and Probabilistic Constructions
Reading: lecture notes #5
- 2018-12-13, Moni: Cuckoo Hashing, k-Wise Independence
and Extractor Constructions
Reading: class slides
- 2018-12-20, Robi: Importance Sampling and Coresets for
Clustering
Reading: lecture notes #7, see also
[MR, chapters 11.2], [Munteanu and
Schwiegelshohn, survey on coresets]
- 2018-12-27, Robi: Coresets via Uniform and Importance
Sampling
Reading: lecture notes #8, see also
[Munteanu
and Schwiegelshohn, survey on coresets]
- 2019-01-03, Robi: Edge-Sparsification of Hypergraphs and Some
Occupancy Problems
Reading: lecture notes #9, see also
[MR, chapters 3.1, 3.2, 3.6 and 4.1], [DP, chapter 1.6]
- 2019-01-10, Moni: TBA
- 2019-01-17, Moni: TBA
- 2019-01-24, Moni: TBA
- 2019-01-31, Robi: Dimension Reduction in l_2
Reading: lecture notes #13
Further reading: [Dasgupta
and Gupta], [Jiri
Matousek (lecture notes), chapter 2]
- 2019-02-07, Robi: The JL Transform and Oblivious Subspace
Embedding
Reading: lecture notes #14
Further reading: [Woodruff,
section 2, also as arXiv:1411.4357]
Assignments
(Should usually be turned in within two weeks)
Reading material
Relevant textbooks:
Similar courses (many with lecture notes):
Useful references: