Welcome to Randomized Algorithms CS 134 for Fall 2026.

Lectures: Tuesdays and Thursdays 9:30 - 10:45am in ILP 3314.
Professor Eric Vigoda vigoda (at) ucsb (use email, not Canvas)
Sections: Fridays Noon-1pm in ILP 3101. (scheduled exams will be held in sections.)
TA: Ved Pradhan

Textbook (recommended): Probability and Computing by Michael Mitzenmacher and Eli Upfal [MU].
Gradescope: Homeworks will be submitted via Gradescope. You will be added automatically via Canvas.
Ed Discussion: Used for class discussion. You will be added automatically via Canvas.

Grading scheme:

Homeworks: 30% (out: Thursdays, due: following Wednesday night)
HWs submitted via Gradescope. Need to be typed in LaTeX (can use overleaf).
Exams: 40%
Tentative dates:
Exam 1: Friday, October 16
Exam 2: Friday, November 13
Project: 30%
Due the last day of instruction.

Lecture schedule:

Lecture 1 (Th 9/24):
Verifying Matrix Multiplication and Polynomial Multiplication
Reading: Lecture notes; see also [MU] Chapters 1.1-1.3
Lecture 2 (Tu 9/29):
Karger's Min-Cut Algorithm
Reading: Lecture notes; see also [MU] Chapter 1.5
Lecture 3 (Th 10/1):
Randomized QuickSort and QuickSelect: Expected Runtime
Reading: Lecture notes; see also [MU] Chapter 2.5