Course Identification
Randomized Algorithms
Lecturers and Teaching Assistants
Prof. Robert Krauthgamer, Prof. Moni Naor
Course Schedule and Location
Thursday, 14:15 - 17:00, Ziskind, Rm 1
08/11/2018
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; 3.00 points
Mathematics and Computer Science (Systems Biology / Bioinformatics): Lecture; Elective; 3.00 points
Prerequisites
Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level.
Attendance and participation
Scheduled date 1
25/02/2019
Estimated Weekly Independent Workload (in hours)
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.
Learning Outcomes
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.