Course page for CS5120 - Probability in Computing

Back to my teaching page

Division of credit:

Assignments: 10%, Attendance: 10%, Programming Assignments: 25% Quizzes: 20%, Final Exam:35%

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: Some randomized algorithms, derandomization III: Markov chains and random walks, with applications.
Main Reference: Probability and Computing by Mitzenmacher and Upfal

Old course notes and References

Part 1 (Seg 12)
Lecture 1 (Karger's algorithm) Illustration of repeated edge contraction here
Lecture 6 (Randomized Median-find)
Chernoff Bounds
Set Balancing and Network Routing
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)
Counting elements in a stream Note on order statistics
Mean Estimation from Samples; Analysis of Morris'algorithm
AMS algorithm and analysis BJKST algorithm for counting distinct elements
Misra-Gries algorithm for heavy hitters
Count-Min algorithm
Method of conditional expectation: 3-SAT
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)

Academic Honesty Policy

Attendance Policy: See here .