CS 574: Randomized Algorithms — Fall 2026

Sariel Har-Peled (sariel at illinois.edu)

Lectures & Schedule

#DayDateTopic / NotesPDF
1WednesdayAugust 26, 2026Introduction
2FridayAugust 28, 2026Some probability: conditional probability, independence, expectation, linearity of expectation, Markov's inequality02_expectations
3WednesdaySeptember 02, 2026Chebychev inequality04_chebychev
4FridaySeptember 04, 2026Quick sort in expectations; Verification03_quick_sort
05_verify
5WednesdaySeptember 09, 2026Occupancy06_occupancy
6FridaySeptember 11, 2026$k$-wise Independence07_k_wise
7WednesdaySeptember 16, 2026Hashing08_hashing
8FridaySeptember 18, 2026Closest pair; Turán's theorem; Derandomization of 3SAT via conditional expectations09_closest_pair
17_turan
18_3sat_derand
MT1WednesdaySeptember 23, 2026▶ Midterm 1 (in class) — info
10FridaySeptember 25, 2026Discrepancy and derandomization16_discrepancy
11WednesdaySeptember 30, 2026Routing on the hypercube; Martingales14_chernoff_app
19_martingales
12FridayOctober 02, 2026Martingales 220_martin_II
13WednesdayOctober 07, 2026Power of two choices21_two_choices
14FridayOctober 09, 2026Power of two choices part II
15WednesdayOctober 14, 2026Streaming25_streaming
16FridayOctober 16, 2026Frequency estimation26_frequency_est
17WednesdayOctober 21, 2026Frequency estimation 227_freq_est_2
MT2FridayOctober 23, 2026▶ Midterm 2 (in class) — info
19WednesdayOctober 28, 2026Random walk II / Random walk III30_rwalk_II
31_rwalk_III
20FridayOctober 30, 2026Random walk III31_rwalk_III
21WednesdayNovember 04, 2026Random walk IV32_rwalk_IV
22FridayNovember 06, 2026Expanding graphs; Random walk V; Graph algebra23_expanding_graphs
34_rwalk_V
33_graph_algebra
23WednesdayNovember 11, 2026Random walk continued
24FridayNovember 13, 2026Johnson-Lindenstrauss Lemma24_jl
25WednesdayNovember 18, 2026Entropy; Entropy II41_entropy
42_entropy_II
26FridayNovember 20, 2026Shannon's theorem43_entropy_III
—Thanksgiving Break — Give thanks, go on vacation
MT3WednesdayDecember 02, 2026▶ Midterm 3 (in class) — info
28FridayDecember 04, 2026
29WednesdayDecember 09, 2026Last lecture