CSCI 328 SP26: Algorithms for Big Data - Mayank Goswami
Playlist
Section titled “Playlist”Lecture Notes
Section titled “Lecture Notes”- 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/30/2026) - Frequency Estimation (Heavy Hitters); Count-Min Sketch
- Lecture 18 (04/13/2026) - Frequency Moments; AMS Sampling Algorithm
- Lecture 19 (04/15/2026) - AMS Sampling: Guarantee Boosting; Counting Distinct Elements; Uniform RV
- Lecture 20 (04/22/2026) - Finish Counting Distinct Elements; Uniform RV; Introduce Flajolet-Martin
- Lecture 21-22 (04/27/2026) - Finish Counting Distinct Elements: Flajolet-Martin Factor-32, Epsilon; Online Algorithms
- Lecture 23 (05/04/2026) - List Update Problem (3 Algorithms); Introduce Multiplicative Weight Updates
- Lecture 24 (05/06/2026) - Prove MWU Expert’s Theorem (Potential Function); Introduce Paging Problem
- Lecture 25 (05/11/2026) - Finish Paging; Dimensionality Reduction & Johnson-Lindenstrauss Lemma; Introduce Nearest Neighbor Search
- Lecture 26 (05/13/2026) - Approximate Nearest Neighbor; Locality Sensitive Hashing; Course Review
Midterm Resources
Section titled “Midterm Resources”- Midterm Prep: Formulas & Identities Sheet
- Midterm Prep: Basic Understanding Problem Sets
- Example 1 of Past Midterm
- Example 2 of Past Midterm