Course page for CS5120 - Probability in Computing

Back to my teaching page

New Division of credit:

Assignments: 15%, Attendance: 10%, Quizzes: 5%, Exam 1:15%, Exam 2(Final):55%
Old Division of credit: Assignments: 10%, Attendance: 10%, Quizzes: 10%, Exam 1:15%, Exam 2:15%, Exam 3(Final):40%

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 and random walks, with applications.

Course Notes and References

Part 1 (Seg 12)
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
References for Part 1
Probability and Computing by Mitzenmacher and Upfal
Randomized Algorithms by Motwani and Raghavan
Randomized Algorithms by Prof. Surendar Baswana, IIT Kanpur
Algorithmic Superpower Randomization by Prof. Bernhard Haeupler
Part 2 (Seg 34)
Feb 11 (Lec 11): Counting elements in a stream
Note on order statistics
Feb 21 (Lec 13): Mean Estimation from Samples;
Analysis of Morris'algorithm
Feb 25 (Lec 14): AMS algorithm and analysis
BJKST algorithm for counting distinct elements
Feb 28 (Lec 15): Misra-Gries algorithm for heavy hitters
Mar 3 (Lec 16): Count-Min algorithm
Mar 3, 6 (Lec 16-17): Method of conditional expectation: 3-SAT
Mar 6,Mar 17 (cancelled) (Lec 17-18): Conditional expectation: Cuts and games
References for Part 2
Algorithms for Big Data by Chandra Chekuri
Sublinear and streaming algorithms by Paul Beame
Part 3 (Seg 56)
Markov Chains: Note 1 & Video 1
Algorithms for 2-SAT & 3-SAT: Note 2
Video 2: part A & Video 2: part B
USTCON: randomized logspace Note 3
Video 3: part A & Video 3: part B
Counting DNF solutions Note 4
Video 4
Counting independent sets and Metropolis algorithm Note 5
Video 5: part A Video 5: part B Video 5: part C
References for Part 3
Notes on probability and computing by Ryan O'Donnell (Lec 14-16 for Markov Chains)
NPTEL videos by Prof. Benny George (Lec 16 onwards for Markov chains)


Assignment One
Assignment Two
Assignment Three
Assignment Four

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.