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: Probability tools, with algorithmic applications.
II: Data streams
III: Markov chains, random walks, applications to sampling and approximate counting.
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
(iii) Algorithms for Big Data by Chandra Chekuri
(iv) Sublinear and streaming algorithms by Paul Beame

Course Notes

Jan 3: Lecture 1 (Karger's algorithm) Illustration of repeated edge contraction here
Jan 21: Lecture 6 (Randomized Median-find)
Jan 28 (Lec 8): Chernoff Bounds
Jan 31 (Lec 9): Set Balancing and Network Routing
Feb 4 (Lec 10): Network Routing
Feb 11 (Lec 11): Counting elements in a stream ; Note on order statistics
Feb 21 (Lec 13): Coming soon...analysis of Morris'algorithm and median-of-means
Feb 25 (Lec 14): Coming soon...AMS and BJKST algorithms for counting distinct elements


Assignment One
Assignment Two

Division of credit:

Assignments: 10%, Attendance: 10%, Quizzes: 10%, Exams: 70% (15+15+40)

Academic Honesty Policy

Attendance Policy:
Minimum is 14 classes and carries 5 marks. Every additional 2 classes carries 1 mark, till a max of 10.