CSCI 328 - Algorithms for Big Data SP26 - Mayank Goswami

Playlist

Lecture 2 (01/28/2026) - Random Variables; Expected Value; Variance; Binomial Distribution
Lecture 3 (02/02/2026) - Independence; Geometric RV; Coupon Collector; Membership Problem (introduce HWC)
Lecture 4 (02/04/2026) - Continue Hashing With Chaining; Introduce Markov’s & Chebyshev’s Inequalities
Lecture 5 (02/09/2026) - Apply Chebyshev’s to HWC; Briefly Introduce Chernoff Bound; Introduce FKS Hashing
Lecture 6 (02/11/2026) - FKS Hashing: Analysis of Preprocessing Time
Lecture 7 (02/18/2026) - More Probability: The birthday paradox; Balls and bins
Lecture 8 (02/23/2026) - Max Load in Balls & Bins; Chernoff bounds; Apply Chernoff to HWC
Lecture 9 (02/25/2026) - Apply Chernoff to HWC; Introduce Linear Probing, Cuckoo Hashing
Lecture 10 (03/02/2026) - Analyze Linear Probing query/insertion time
Lecture 11 (03/04/2026) - Introduce Bloom Filters
Lecture 12 (03/09/2026) - Finish Bloom Filter; Introduce Streaming Algorithms & Uniform Sampling
Lecture 13 (03/11/2026) - Streaming: Approximate Counting; Epsilon-Delta Guarantee; Morris Counter
Lecture 14 (03/16/2026) - Textbook Problems from Mitzenmacher (4.9 & 4.5): Mean Estimation; Median of Weak Estimates; Fraction Estimation
Lecture 15 (03/18/2026) - Epsilon-Delta Approximate Median; Morris+ and ++; Variance of Morris Counter
Lecture 16: Repeat of Lecture 14
Lecture 17 (03/23/2026) - Frequency Estimation (Heavy Hitters); Count-Min Sketch