CS 574: Randomized Algorithms — Fall 2026

Sariel Har-Peled (sariel at illinois.edu)

Lectures & Schedule

#DayDateTopic / NotesMaterials
1WednesdayAugust 26, 2026Introductionintro
2FridayAugust 28, 2026Some probability: conditional probability, independence, expectation, linearity of expectation, Markov's inequalityexpectations
3WednesdaySeptember 02, 2026Quick sort in expectations; Verificationquick_sort
verify
4FridaySeptember 04, 2026Chebychev inequalityalias_method
chebychev
recording
youtube
5WednesdaySeptember 09, 2026Occupancyoccupancy
6FridaySeptember 11, 2026$k$-wise Independencek_wise
7WednesdaySeptember 16, 2026Verifying identitiesverify
8FridaySeptember 18, 2026Treaps, Turán's theoremtreaps
turan
MT1WednesdaySeptember 23, 2026▶ Midterm 1 (in class) — infomock exam
solution
10FridaySeptember 25, 2026Closest pairclosest_pair
11WednesdaySeptember 30, 2026Chernoff inequality, Routing on the hypercubechernoff
chernoff_app
12FridayOctober 02, 2026Routing in the hypercube, discrepancychernoff_app
discrepancy
13WednesdayOctober 07, 2026Martingalesmartingales
martin_II
summary
slides
14FridayOctober 09, 2026Power of two choices part II
15WednesdayOctober 14, 2026Streamingstreaming
slides
16FridayOctober 16, 2026Frequency estimationfrequency_est
slides
17WednesdayOctober 21, 2026Frequency estimation 2freq_est_2
slides
MT2FridayOctober 23, 2026▶ Midterm 2 (in class) — info
19WednesdayOctober 28, 2026Finite Metric Spaces and Partitionspartitions
slides (15 min)
slides (75 min)
20FridayOctober 30, 2026FMS/Partitions continued
21WednesdayNovember 04, 2026Dimension reduction and the Johnson–Lindenstrauss lemmajl
slides (15 min)
slides (mid-length)
slides (75 min)
slides (geometry behind JL)
22FridayNovember 06, 2026Entropy, Randomness, and Compressionentropy
entropy_II
slides (15 min)
slides (mid-length)
slides (75 min)
23WednesdayNovember 11, 2026Entropy III: Shannon’s Theorementropy_III
slides (15 min)
slides (mid-length)
slides (75 min)
24FridayNovember 13, 2026Min Cut and Max Cutmincut
max_cut
slides (75 min)
25WednesdayNovember 18, 2026Entropy; Entropy IIentropy
entropy_II
26FridayNovember 20, 2026Shannon's theorementropy_III
—Thanksgiving Break — Give thanks, go on vacation
MT3WednesdayDecember 02, 2026▶ Midterm 3 (in class) — info
28FridayDecember 04, 2026
29WednesdayDecember 09, 2026Last lecture