Links: scribe template, lecture video playlist (must be logged into YouTube with @berkeley.edu account to view).

Lecture Schedule

Lec# Date Topic Scribe(s)
1 Tuesday, 1/17/23 logistics, course topics, single-source shortest paths w/ negative edges
(price fns, scaling, Bernstein-Nanongkai-WulffNilsen) pdf tex imgvid		 Altan Haan
2 Thursday, 1/19/23 BNW wrap-up, scaling for max flow pdf tex imgvid Sanjay Gollapudi
Andrew Lin
3 Tuesday, 1/24/23 blocking flow, link-cut treespdf texvid Alejandro Sanchez
Sohom Paul
4 Thursday, 1/26/23 amortized analysis, splay treespdf teximgvid Nishant Bhakar
Ryan Zhu
5 Tuesday, 1/31/23 implementing link-cut trees using splay trees, O(log2n) analysis via preferred-path and heavy-light decompositionspdf texvid Jonathan Pei
Vibhav Athreya
6 Thursday, 2/2/23 link-cut trees analysis wrap-up, min-cost max flow pdftexvid Sanjay Subramanian
Kelvin Lee
7 Tuesday, 2/7/23 binomial heaps, Fibonacci heaps pdfteximgvid Chris Liu
Serena Zhang
8 Thursday, 2/9/23 word RAM model, van Emde Boas trees, x-fast and y-fast tries pdf teximgvid Kishan Jani
Wilson Wu
9 Tuesday, 2/14/23 y-fast tries wrap-up, fusion trees pdfteximgvid Martin Toft
10 Thursday, 2/16/23 most significant set bit, Chernoff bound, load balancing, linear probing pdfteximgvid Rohit Agarwal
11 Tuesday, 2/21/23 Chernoff bound wrap-up, k-wise independence, linear probing analysis pdftexvid Amar Shah
12 Thursday, 2/23/23 linear probing with 5-wise independence, symmetrization, approximate membership pdfteximgvid Matthew Ding
Jonathan Tay
13 Tuesday, 2/28/23 Bloom filters, cuckoo hashing pdftexvid Anna Deza
Alec Li
14 Thursday, 3/2/23 power of two choices, online algorithms pdfteximgvid Eshaan Bhansali
Nikki Suzani
15 Tuesday, 3/7/23 deterministic and randomized paging, resource augmentation pdftexvid Vaibhav Agrawal
Eric Nguyen
16 Thursday, 3/9/23 weighted paging, linear program duality, online primal dual pdfteximgvid Laryn Qi
Brandon Tran
17 Tuesday, 3/14/23 online primal/dual wrap-up, approx algorithms (weighted set cover) pdftexvid Aadil Manazir
18 Thursday, 3/16/23 vertex cover, integrality gaps, PTAS/FPTAS pdftexvid Nate Tausik
19 Tuesday, 3/21/23 PTAS/FPTAS for knapsack, DNF-counting pdftexvid Calvin Yan
Young Jin Park
20 Thursday, 3/23/23 semidefinite programming, max-cut, streaming algorithms pdftexvid Ajit Kadaveru
Lance Mathias
Tuesday, 3/28/23 Spring break
Thursday, 3/30/23 Spring break
21 Tuesday, 4/4/23 simplex method pdfteximg vid Hanzhe Wu
Chethan Bhateja
22 Thursday, 4/6/23 strong duality, complementary slackness, ellipsoid pdfteximg vid Sudhanva Kulkarni
23 Tuesday, 4/11/23 interior-point methods, Newton’s method pdfteximgvid Johannes Pfannschmidt
24 Thursday, 4/13/23 Guest lecture: Michael Kim, fairness and multicalibration pdfteximg Alex Fu
25 Tuesday, 4/18/23 spectral graph theory, Laplacians, Cheeger’s inequality pdftexvid Andrew Huang
26 Thursday, 4/20/23 normalized laplacians, proof of Cheeger’s inequality pdftexvid Yang Han
27 Tuesday, 4/25/23 Guest lecture: Ryan Williams, hardness within P pdfvid Espen Fosseide
28 Thursday, 4/27/23 chronogram technique: dynamic partial sums pdfteximgvid