Course page for CS5120 - Probability in Computing

Back to my teaching page

Course Information


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.

References:
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

Course Notes

Slides of Lecture 1: Part One , Part Two

Assignments

N/A

Division of credit:

Assignments: 10%, Attendance: 10%, Quizzes: 20%, Exams: 60%.

Academic Honesty Policy