[Course description] [Announcements] [Lectures] [Assignments] [Reading material]
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:
http://www.wisdom.weizmann.ac.il/~robi/teaching/2011a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2013a-RandomizedAlgorithms