Lecture notes would be hopefully updated before (and probably
sometime after lecture). All notes in one
huge file.
Scribbles \& notes
- L01: Introduction
[scribbles,
notes,
recording], 01/18/22.
- L02: Some probability
[scribbles,
notes,
recording],
01/20/22.
Probability, conditional probability, independence,
expectation, linearity of expectation, Markov's
inequality. Approximating \(k\)-SAT.
- L03: Quick sort via expectations, and Chebychev's inequality
Notes:
- QuickSort and QuickSelect via expectations
- Chebychev's inequality,
sampling, and faster selection
- L04: Verification, Schwartz–Zippel lemma, some complexity
[Notes].
- L05: Evaluating And/Or Trees, and closet pair.
[AND/OR Notes,
closest pairs Notes].
- L06: The Birthday Paradox, Occupancy and the Coupon Collector
Problem
[Notes,
scribbles,
recording], 02/03/22.
- L07: More coupons, conditional expectation and
concentration, quick sort with high probability, 2/8/22.
- Notes:
Coupon's Collector Problems II.
- Notes:
Conditional Expectation and Concentration
- Notes:
Quick Sort with High Probability
- L8: Concentration of Random Variables -- Chernoff's Inequality,
2/10/22.
[Notes].
- L9: Applications of Chernoff's Inequality, 2/15/22.
[Notes].
- L10: Min Cut, 2/17/22.
[Notes].
- L11: Turán's theorem (independent set), Discrepancy,
Derandomization, 02/22/2022.
-
Notes on discrepancy.
-
Notes on
independent set and Turán's theorem.
- L12: Method of conditional expectations, and Martingales, 2/24/22.
[scribbles,
recording]
- Derandomization using Conditional Expectations
[Notes].
- Martingales
[Notes].
- L13: More on martingales, 3/1/22.
[Notes].
- L14: Martingales II & The power of two choices
[Notes].
- L15: More on two choices, and $k$-wise independence, 3/8/22.
[Notes].
- L16: Expanding graphs.
[Notes], 3/10/22.
- L17: Dimension Reduction
[Notes], 3/22/22.
- L18: Streaming and the Multipass Model
[Notes], 3/24/22.
- L19: Frequency Estimation over a Stream
[Notes], 3/29/22.
- L20: Streaming continued, 3/31/22.
- L21: Approximating the Number of Distinct Elements in a Stream
[Notes],
4/5/22.
- L22: Locality sensitive hashing
[Notes], 4/7/22.
- L23: Random walk I, 4/12/22
[Notes].
Walking on the integer line, walking on the 2d grid, walking
on the 3d grid.
- L24: Random walk II, 4/14/22
[Notes]
2SAT via random walk.
Markov chains
- L25: Random walk III, 4/19/22
[Notes].
- L26: Random walk IV, 4/21/22
[Notes].
- L27: Random walk V, 4/26/22
- A Bit on Algebraic Graph Theory
[Notes].
- More on random walks
[Notes].
- L28: Last lecture: Roads not traveled
- May 3: Final exam
- May 5: Reading day.
Notes for additional topics
- L34: Complexity classes
[Notes].
- L35: Hashing
[Notes].
- L36: Backwards analysis
[Notes].
- L37: Multiplicative Weight Update: Expert Selection
[Notes].
- L38: On Complexity, Sampling, and $\eps$epsilon-Nets and
$\eps$eps-Samples
[Notes].
- L39: Double sampling
[Notes].
- L40: Finite Metric Spaces and Partitions
[Notes].
- L41: Entropy, Randomness, and Information
[Notes].
- L42: Entropy II
[Notes].
- L43: Entropy III - Shannon's Theorem
[Notes].
- L44: Approximate Max Cut
[Notes].
- L45: Expanders I
[Notes].
- L46: Expanders II
[Notes].
- L47: Expanders III - The Zig Zag Product
[Notes].
- L48: The Probabilistic Method
[Notes].
- L49: The Probabilistic Method III
[Notes].
- L50: The Probabilistic Method IV
[Notes].
- L51: Sampling and the Moments Technique
[Notes].
- L52: Primality testing
[Notes].
- L53: Talagrand's Inequality
[Notes].
- L54: Low Dimensional Linear Programming
[Notes].
- L55: Algorithmic Version of \Lovasz Local Lemma
[Notes].
- L56: Some math stuff
[Notes].
Previous semester notes
A good starting point is lecture notes from previous semesters:
Last modified: Sat 2022-04-30 18:03:58 UTC 2022 by Sariel Har-Peled