Course page for CS5120 - Probability in Computing
The course will focus on tools from probability and their applications to algorithms.
Topics to be covered:
I: Review of basic probability, random variables, expectation, concentration inequalities,
with algorithmic applications.
II: More applications: data streams, geometric algorithms, randomized rounding.
III: Markov chains, random walks, applications to sampling and approximate counting.
IV: Pairwise independence & derandomization.
1. Probability and Computing by Mitzenmacher and Upfal
2. Randomized Algorithms by Motwani and Raghavan
3. Courses elsewhere with similar or related content:
(i) Randomized Algorithms
by Prof. Surendar Baswana, IIT Kanpur
(ii) Algorithmic Superpower Randomization
by Prof. Bernhard Haeupler
Division of credit:
Assignments: 10%, Attendance: 10%,
Quizzes: 20%, Exams: 60%.