CSCE 689: Special Topics in Modern Algorithms for Data Science
- Instructor: Samson Zhou
- Lectures: MWF 08/21/2023-12/12/2023, 1:50-2:40 PM CT, HRBB 126
- Office hours: Wednesday, 3:00-4:00 PM CT, PETR 424, or by appointment
Course Description
Algorithms for data science; sublinear algorithms; models of computation for big data; differential privacy.
Full syllabus here.
Grading
Scribe notes, i.e., succinct LaTeX summary of lectures 20%, midterm presentation 35%, final project 45%
Course Schedule
- Week 1: Probability basics (hashing, birthday paradox, balls-in-bins)
- Week 2: Probability basics continued (max load, coupon-collector), concentration inequalities (Markov, Chebyshev, Chernoff)
- Week 3: Dimensionality reduction (Johnson-Lindenstrauss)
- Week 4: Streaming model, reservoir sampling, heavy-hitters (Misra-Gries, CountMin)
- Week 5: Streaming model continued, heavy-hitters (CountSketch), norm estimation
- Week 6: Reading paper presentations
- Week 7: Streaming model continued, sparse recovery, distinct elements
- Week 8: Streaming model continued, distinct elements, L0 sampling
- Week 9: Graphs in the streaming model, matchings, connectivity, bipartiteness
- Week 10: Clustering in the streaming model, coresets
- Week 11: Sliding window model, adversarial robustness
- Week 12: Property testing, linear regression
- Week 13: Subspace embeddings, differential privacy
- Week 14: Learning-augmented algorithms
- Week 15: Project presentations
Additional Course Materials
Flyer
Full Syllabus
Project Reading List
LaTeX Template
Scribe List
There is no textbook for this class.
However, the following materials may be useful as reference materials:
- Course Notes and Videos:
- Monographs:
Extra Slides: Guest Slides 1 (ppt),
Guest Slides 2 (ppt),
Guest Slides 3 (ppt)