MCS 549 - Mathematical Foundations of Data Science
University of Illinois at Chicago
Fall 2026

This course covers the mathematical foundations of modern data science from a theoretical computer science perspective. Topics will include random graphs, random walks, Markov chains, streaming algorithms, learning theory, clustering, singular value decomposition, and random projections.

Basic Information

Syllabus: pdf
Time and Location: M-W-F 9:00-9:50 am, 101 Stevenson Hall (SH)
Instructor: Lev Reyzin, SEO 417
Online Textbook: Avrim Blum, John Hopcroft, and Ravi Kannan, Mathematical Foundations of Data Science
Office Hours: T 11:00-11:50am (online), F 11:00-11:50am (in-person)

Presentations

instructions
topics and times

Problem Sets

problem set 1 due 10/2/26
problem set 2 due 11/2/26
problem set 3 due 12/4/26

Lectures and Readings

lecture 1 (8/24/26)
covered material: intro to the course, preview of the material
reading: chapter 1

lecture 2 (8/26/26)
covered material: some concentration inequalitiess
reading: chapters 2.1 - 2.2

lecture 3 (8/28/26)
covered material: geometry in high dimensions, the unit ball, sampling from a high-dimensional sphere
reading: chapters 2.3 - 2.5

lecture 4 (8/31/26)
covered material: Gaussian annalus theorem, random projections and the Johnson-Lindesnstrauss (JL) lemma
reading: chapters 2.6 - 2.7

lecture 5 (9/2/26)
coveredmaterial: singular value decomposition (SVD), best-fit subspaces, and optimality of greedy algorithm
reading: chapters 3.1 - 3.4

lecture 6 (9/4/26)
covered material: computing SVD, power iteration, separating Gaussians
reading: chapters 3.7 - 3.9

lecture 7 (9/9/26)
covered material: applications of JL
reading: N/A

lecture 8 (9/11/26)
covered material: SVD in recommender systems
reading: N/A

lecture 9 (9/14/26)
covered material: intro to Markov chains, stationary distribution, Fundamental Theorem of Markov Chains
reading: chapter 4 intro, 4.1

lecture 10 (9/16/26)
covered material: Markov chain Monte Carlo (MCMC), Metropolis-Hasting, Gibbs Sampling
reading: chapter 4.2

lecture 11 (9/18/26)
covered material: volume estimation of convex bodies
reading: chapter 4.3

lecture 12 (9/21/26)
covered material: bounding mixing time with normalized conductance
reading: chapter 4.4

lecture 13 (9/23/26)
covered material: electrical networks and random walks, harmonic functions
reading: begin chapter 4.5

lecture 14 (9/25/26)
covered material: probabilistic interpretation of voltage, current, and effective resistence
reading: finish chapter 4.5

lecture 15 (9/28/26)
covered material: hitting and commute times on unweighted graphs
reading: chapter 4.6

lecture 16 (9/30/26)
covered material: cover time, random walks on lattices, the web as a Markov Chain
reading: chapters 4.7 and 4.8

lecture 17 (10/2/26)
covered material: intro to machine learning, PAC learning
reading: chapter 5.1

lecture 18 (10/5/26)
covered material: Occam's razor theorem
reading: chapter 5.4

lecture 19 (10/7/26)
covered material: VC dimension
reading: chapter 5.5

lecture 20 (10/9/26)
covered material: SVM, part I
reading: begin Support-Vector Networks by Cortes and Vapnik

lecture 21 (10/12/26)
covered material: SVM, part II
reading: finish Support-Vector Networks by Cortes and Vapnik

lecture 22 (10/14/26)
covered material: kernel functions
reading: chapter 5.3

lecture 23 (10/16/26)
covered material: weak learning, boosting the accuracy, AdaBoost
reading: chapter 5.11

lecture 24 (10/19/26)
covered material: margins in boosting
reading: Boosting the margin: A new explanation for the effectiveness of voting methods by Schapire, Freund, Bartlett, and Lee

lecture 25 (10/21/26)
covered material: the Perceptron algorithm, online learning
reading: chapter 5.2

lecture 26 (10/23/26)
covered material: neural networks, deep learning, and LLMs
reading: chapter 5.8

lecture 27 (10/26/26)
covered material: introduction to random graphs, counting triangles
reading: chapter 8.1

lecture 28 (10/28/26)
covered material: first and second moment methods, sharp thresholds, diameter 2
reading: chapter 8.2

Lecture 29 (10/30/26)
covered material: isolated vertices, Hamiltonian cycles, replicators and increasing properties
reading: chapter 8.5

Lecture 30 (11/2/26)
covered material: the Molloy-Reed condition, other growth models
reading: chapters 8.8 and 8.9

Lecture 31 (11/4/26)
covered material: intro to streaming algorithms, estimating the number of distinct elements in a stream
reading: chapter 6.1

Lecture 32 (11/16/26)
covered material majority element, and estimating second frequency moment of a stream
reading: chapter 6.2