Lecturers and Teaching Assistants
Prof. Robert Krauthgamer, Prof. Moni Naor
Course Schedule and Location
Monday, 14:15 - 17:00, Ziskind, Rm 1
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; Regular; 3.00 points
Attendance and participation
Estimated Weekly Independent Workload (in hours)
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.
Upon successful completion of this course students should be able to:
- Analyze probabilistic events and randomized processes.
- Design algorithms that use randomness, and analyze their performance.
- Make use of basic tools such as first and second moment, concentration bounds, balls and bins, birthday paradox.
- Describe and apply algorithmic paradigms that rely on randomness like hashing, sampling, sketching, and streaming.