Schedule/notes for CS 574 Randomized Algorithms (sp22)

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:
  1. QuickSort and QuickSelect via expectations
  2. 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.
  1. Notes: Coupon's Collector Problems II.
  2. Notes: Conditional Expectation and Concentration
  3. 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

• Fall 2019
• Spring 2018