CSCI 4030/6220 Randomized Algorithms

Fall 2026

Overview

Randomness is a powerful algorithmic tool. This course covers the design and analysis of randomized algorithms at the advanced undergraduate / beginning graduate level. The course emphasizes both theoretical analysis and algorithmic design.

Topics covered:

Course Logistics

The syllabus is available as an archival pdf.

Instructor: Alex Gittens (gittea at rpi dot edu)

Lectures: MTh 12pm–1:50pm ET, Sage 5101

Office Hours: Lally 316, Thursday 3–5pm ET

Course discussions and announcements are available on Piazza. You are responsible for keeping up with Piazza for announcements.

Course Materials

The primary text is Mitzenmacher & Upfal, Probability and Computing (2nd ed., Cambridge, 2017). Supplementary text:

Lecture Notes

Each available lecture has two PDFs: a Handout for self-study and a Presentation with progressive reveals for class.

Prelude
L0 Course overview and logistics ▼

Course logistics; grading; reading expectations; homework workflow; course prerequisites; why randomized algorithms matter; how lecture, reading, and assignments fit together.

Reading: course syllabus and introductory notes

Part 1: Foundations
L1 Why randomize? ▼

Course intro; Freivalds' matrix verification (1977); Quicksort (Hoare, 1962); MC vs. LV vocabulary; the \(A(x;r)\) model; one-sided amplification by repetition.

Reading: MU §§1.1--1.3, 2

L2 Indicators, expectation, Quicksort, and hashing ▼

Indicator random variables; linearity of expectation; full expected-comparison analysis of randomized Quicksort (\(2(n+1)H_n-4n\) via pair indicators); a first hashing question via the dictionary/collision/balls-and-bins correspondence; collision probability via union bound.

Reading: MU §1.2 (union bound), §2.1 (expectation, linearity), §2.5 (quicksort analysis)

L3 From expectations to tail probabilities ▼

Variance, covariance, pairwise independence; Markov's inequality; Chebyshev's inequality; converting expected runtime to confidence bounds for Las Vegas algorithms.

Reading: MU §3.1–3.3 (Markov, Chebyshev), §3.5 (randomized median application).

L4 Chernoff bounds and concentration ▼

Why Chebyshev leaves something on the table; changing variables inside Markov's inequality; exponential moments and factorization for independent sums; Bernoulli MGFs; the multiplicative Chernoff upper-tail bound; standard-deviation versus relative-deviation viewpoints; lower-tail symmetry; amplification by repetition; Chernoff bounds applied to routing and edge-load arguments.

Reading: MU §4.1–4.2 (MGF, Chernoff for Bernoulli sums)

Part 2: Canonical Algorithms and Data Structures
L5 Hash tables and extreme bucket loads ▼

Hashing notation from Lecture 2; separate chaining; bucket loads; the worst-bucket question; the maximum-load scale for \(n\) balls into \(n\) bins; Poissonization as an analysis device.

Reading: MU §5.1–5.5 (balls and bins, Poisson approximation, hashing)

L6 The power of two choices ▼

The one-choice baseline; the adaptive two-choice rule; heavy-bin counts and level-by-level state compression; the recurrence for the fraction of heavy bins; the \(\log\log n\) maximum-load bound.

Reading: MU §17.1–17.3 (power of two choices)

L7 From ideal random functions to implementable hash families ▼

The implementation problem hidden in the ideal hash model; universal hashing; pairwise and \(k\)-wise independence; affine finite-field families; the proof principle of using only the randomness the analysis actually needs.

Reading: MU §15.1–15.3 (pairwise independence, universal hashing)

L8 Cuckoo hashing: worst-case lookup in a dynamic hash table ▼

The limitation of static FKS under insertions; two hash locations per key; the displacement rule; the cuckoo graph; feasibility via component structure; rehash-on-failure and expected efficient updates.

Reading: MU §17.4 (cuckoo hashing)

L9 Fingerprints and Bloom filters ▼

Fingerprinting for set membership; Bloom filters and false-positive analysis; the optimal number of hash functions; the space/accuracy/confidence tradeoff.

Reading: MU §5.5.3 (Bloom filters)

L10 Streaming I: frequency estimation ▼

The one-pass streaming model; Misra–Gries cancellation and its deterministic additive-error guarantee; Count-Min sketch as randomized collision control, with the one-sided point-query bound \(\hat f_i \le f_i + \epsilon\|f\|_1\) w.p. \(1-\delta\); the reusable proof pattern (expected error \(\to\) constant success \(\to\) independent amplification); the accuracy/space/confidence tradeoff.

Reading: MU §15.4 (count-min sketch)

Exam 1
In-class exam Relevant lectures: 1-7
L11 Streaming II: moment and distinct-count sketches ▼

Global statistics from tiny sketches; the AMS \(F_2\) estimator from random-sign cancellation: unbiasedness and variance bound; averaging plus median-of-means amplification to \((1\pm\epsilon)\) accuracy with failure probability \(\delta\); Flajolet–Martin distinct counting from rare hash events and its occupancy boundary.

Part 3: Graphs and the Probabilistic Method
L12 Randomized graph algorithms I: Karger min-cut ▼

Global min-cut by random edge contraction; single-run success probability \(\ge 1/\binom{n}{2}\); amplification by repetition; the Karger–Stein recursive contraction (stated and sketched, \(O(n^2 \log^3 n)\) w.h.p.); corollary: a graph has \(O(n^2)\) minimum cuts.

L13 Randomized graph algorithms II: graph sparsification ▼

Cut sparsification vs. uniform sampling; edge strength and inverse-strength sampling; projection counting; strength-sum inequality; the connection from cut counting to projection counting and from graph algorithms to RandNLA.

L14 Probabilistic method I: existence via randomness ▼

The probabilistic method: \(\Pr[\text{good}] > 0 \Rightarrow\) a good object exists; the expectation argument for MAX-CUT \(\ge m/2\); the first-moment / union-bound Ramsey bound \(R(k,k) > 2^{k/2}\); alteration (sample first, repair afterward) sharpening the Ramsey bound to \(\Theta(k\,2^{k/2})\).

Reading: MU §6.1 (basic counting argument), §6.2 (expectation argument), §6.4 (sample and modify)

L15 Probabilistic method II: conditional expectation ▼

The method of conditional expectations: converting an existence proof into a deterministic algorithm by walking its decision tree; derandomizing MAX-CUT \(\ge m/2\) via the local greedy rule; MAX-3SAT's \(7/8\) bound; set balancing and pessimistic estimators.

Reading: MU §6.3 (conditional-expectation derandomization of MAX-CUT), §6.2.2 (clause-satisfaction bound), §4.4 (set balancing); Alon & Spencer Ch. 15, Motwani & Raghavan Ch. 5 for pessimistic estimators

L16 Lovász Local Lemma and Moser-Tardos: escaping the union bound ▼

A concrete random construction where the union bound is too crude; modeling bad events and their dependencies; the symmetric Lovász Local Lemma; the Moser–Tardos resampling algorithm; witness trees and expected resampling.

Reading: MU Ch. 6 (Lovász Local Lemma, including the algorithmic LLL sections)

L17 Derandomization: how little randomness does an algorithm need? ▼

The seed model \(A(x;R)\); recognizing which independence a performance proof actually uses; pairwise-independent vertex bits from an \(O(\log n)\)-bit seed; derandomizing MAX-CUT by enumerating polynomially many seeds; why stronger guarantees can require higher-wise independence; contrast with conditional-expectation derandomization.

Reading: MU §15.1 (pairwise-independent bits from short seeds; MAX-CUT derandomization), §15.2.1 (sampling using fewer random bits)

L18 Randomized rounding and approximation ▼

0–1 integer programs and a self-contained LP-relaxation primer; approximation ratios certified by relaxation bounds; Set Cover by independent rounding of the LP optimum \(x^\star\); repetition to drive constraint failures down and Chernoff control of the actual cost, giving the \(O(\log(n/\delta))\) w.h.p. guarantee; Monte Carlo versus Las Vegas variants; derandomization via conditional expectation; MAX-SAT as the contrasting single-round application.

Reading: Williamson & Shmoys, The Design of Approximation Algorithms, Ch. 5; MR Ch. 5

Part 4: Dependent-Process Concentration and RandNLA
L19 Martingales and concentration ▼

Doob martingales from conditional expectations; Azuma–Hoeffding for bounded conditional changes; how edge versus vertex exposure changes concentration bounds for maximum matching and chromatic number in random graphs; McDiarmid’s bounded-differences inequality; process increments versus final-output sensitivity through a stopped-betting example; concentration of optimized facility coverage and best training scores.

Reading: MU Ch. 13 (martingales, Azuma–Hoeffding, Doob martingales, bounded differences)

L20 Learning from random choices ▼

Online route choice and regret against the best fixed route via exponential weights; martingale differences and Azuma’s inequality for dependent random choices; smooth nonconvex optimization and stochastic gradient descent; unbiased sampled gradients and expected stationarity guarantees; high-probability single-run SGD analysis via an exponential supermartingale that adapts to trajectory-dependent noise.

Reading: MU §13.1, §§13.4–13.5 (martingales and Azuma–Hoeffding)

Exam 2
In-class exam Relevant lectures: 10--18
L21 Randomized linear algebra II: Johnson-Lindenstrauss and oblivious subspace embeddings
L22 Randomized linear algebra III: sketched least squares and leverage scores
Part 5: Markov Chains and Sampling
L23 Markov chains I: stationarity, reversibility, detailed balance, Metropolis-Hastings
L24 Markov chains II: mixing time, coupling, conductance intuition
Part 6: Research Projects
L25 Research Presentations
L26 Research Presentations

Lecture notes will be posted here as they become available.

Exams

Exam 1 Solution

In-class Quizzes

Quiz 1 (to be posted)
Quiz 2 (to be posted)
Quiz 3 (to be posted)
Quiz 4 (to be posted)
Quiz 5 (to be posted)
Quiz 6 (to be posted)
Quiz 7 (to be posted)
Quiz 8 (to be posted)

Homeworks

Homework submission: CSCI 4030 and CSCI 6220 (Jupyter notebooks and PDFs).

Late assignments will not be accepted, unless you contact the instructor at least two days before the due date to receive a deferral. Deferrals will be granted at the instructor's discretion.

Homework 1: assignment (PDF) · Posted Wed Sep 2, 2026 · Due Wed Sep 9, 2026, 9:00pm ET

Homework 2: assignment (PDF) · Posted Fri Sep 11, 2026 · Due Fri Sep 18, 2026, 11:59pm ET

Homework 3: assignment (PDF) · Posted Mon Sep 21, 2026 · Due Mon Sep 28, 2026, 11:59pm ET

Homework 4: assignment (PDF) · Posted Sat Sep 26, 2026 · Due Wed Oct 7, 2026, 11:59pm ET

Homework 5: assignment (PDF) · Posted Mon Oct 5, 2026 · Due Wed Oct 14, 2026, 11:59pm ET

Homework 6: assignment (PDF) · Posted Fri Oct 30, 2026 · Due Fri Nov 6, 2026, 11:59pm ET

Homework 7: assignment (PDF) · Posted Mon Nov 9, 2026 · Due Mon Nov 16, 2026, 11:59pm ET

Research Project (CSCI 6220 only)

Graduate students will complete a research project culminating in a presentation and written report. The project must relate to the subject matter of the course. See the project page for details.