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:
- Foundations: Monte Carlo vs. Las Vegas, amplification, review of discrete probability, concentration inequalities (Markov, Chebyshev, Chernoff), limited independence.
- Algorithms and Data Structures: Randomized quicksort/selection, balls and bins, hashing (universal, perfect, cuckoo, Bloom filters), streaming and sketching, randomized graph algorithms
- The probabilistic method and derandomization: the probabilistic method, derandomization and pseudorandomness.
- Advanced Topics: Randomized rounding and approximation, martingales, randomized linear algebra (Kaczmarz, subspace embeddings, sketched least squares, fast Laplacian solvers), Markov chains and mixing.
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:
- Motwani & Raghavan, Randomized Algorithms (Cambridge, 1995)
Lecture Notes
Each available lecture has two PDFs: a Handout for self-study and a Presentation with progressive reveals for class.
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)
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)
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)
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)
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)
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.
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.
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.
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)
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
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)
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)
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
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)
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)
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.