CSCE 658: Randomized Algorithms
- Instructor: Samson Zhou
- Lectures: TR 01/16/2024-05/12/2024, 5:30-6:45 PM CT, HRBB 126
- Office hours: Thursday, 4:15-5:15 PM CT, PETR 424, or by appointment
Course Description
Randomized algorithms; probability theory; algorithms for data science; sublinear algorithms.
Full syllabus here.
Grading
Homework 50%, final exam OR research project 50%
Course Schedule
- Week 1: Polynomial identity testing
- Week 2: Karger's min-cut algorithm, Probability basics (birthday paradox, Markov)
- Week 3: Probability basics continued (coupon collector, max load), concentration inequalities (Chebyshev, Chernoff bounds)
- Week 4: Dimensionality reduction (Johnson-Lindenstrauss), streaming model, reservoir sampling, heavy-hitters)
- Week 5: Streaming model, heavy-hitters (Misra-Gries, CountMin)
- Week 6: Streaming model continued, heavy-hitters (CountSketch), norm estimation, clustering
- Week 7: Clustering, coresets, information theory
- Week 8: Probabilistic method, Lovasz Local Lemma
- Week 9: Spring Break
- Week 10: Homework review, linear programming
- Week 11: Online learning, multiplicative weights
- Week 12: Applications of online learning
- Week 13: Differential privacy (randomized response, basic properties, Laplace mechanism)
- Week 14: Differential privacy (exponential mechanism), martingales, semester review
- Week 15: Distinct elements in the streaming model (optional material), mock final, project presentations
Problem Sets
- Problem Set 1 (Due Thursday, February 1, 2024, 5 pm CT),
PS 1 LaTeX Template
- Problem Set 2 (Due Tuesday, February 20, 2024, 5 pm CT),
PS 2 LaTeX Template
- Problem Set 3 (Due Thursday, March 7, 2024, 5 pm CT),
PS 3 LaTeX Template
- Problem Set 4 (Due Tuesday, April 23, 2024, 5 pm CT),
PS 4 LaTeX Template
Additional Course Materials
Full Syllabus
Project Reading List
Mock Final
There is no textbook for this class.
However, the following materials may be useful as reference materials:
- Course Notes and Videos:
- CSCE 658, Randomized Algorithms, Spring 2016, under Jianer Chen
- CSCE 658, Randomized Algorithms, Spring 2018, under Andreas Klappenecker
- Randomized Algorithms and Probabilistic Analysis, under Gregory Valiant
- Advanced Algorithms, under Anupam Gupta
- Mathematical Toolkit in Computer Science, under Hemanta Maji
- Algorithms for Data Science, under Cameron Musco
- Data Stream Algorithms, under Amit Chakrabarti
- Algorithms for Big Data, under David P. Woodruff
- Monographs: