**Randomized algorithms (Summer 24), Instructor: Laszlo Kozma, Freie Universitaet Berlin

**References (letters refer to author initials, numbers to chapter/section):

[MR] R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995
[MU] M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Second Edition. Cambridge University Press, 2017.
[AS] N. Alon, J. Spencer. The Probabilistic Method. Fourth Edition. Wiley, 2016. 

**General references about algorithms (including randomized), not essential for this course:

[CLRS] T. H. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4th Ed. MIT Press 2022
[KT] J. Kleinberg, E. Tardos. Algorithm Design, Addison-Wesley 2005.


** Topics Covered **    (and relevant source material)

I. Examples of randomized algorithms  (~3 weeks)
  1. Minimum Cut               (MR 1.1, MR 10.2, MU 1.5)
  2. Smallest Covering Disk    (Welzl article + sampling HW)
  3. Long path, Color-Coding   (Alon-Yuster-Zwick paper, notes pdf)
  4. Checker for Graph Isomorphism   (Blum-Kannan paper)
  5. Ski Rental                (notes pdf)

II. Foundations/recap  (~2 weeks)	    		(MR 1-4, A-C, MU 1-4)
  1. Events, probabilities, random variables
  2. Union bound, independence, conditional probability
  3. Expectation, variance
  4. Tail bounds: Markov, Chebyshev
  5. Application: Balls into bins
  6. Application: Selection by sampling (Floyd-Rivest)
  7. Tail bounds: Chernoff
  8. Las Vegas, Monte Carlo, complexity classes
  9. Uses of randomness

III. Probabilistic method (~2 weeks)       (MR 5, MU 5,6, AS)
  1. Probabilistic method introduction, warmup: minimum cut.
  2. Main example: Ramsey numbers -- existence of large graphs avoiding clique and independent set of certain size
  3. Maximum independent set, solutions guaranteed by degree conditions
  4. Random graphs, G(n,p) model, thresholds and sharp thresholds
  5. Example property: "no isolated vertex"; existence of sharp threshold; analysis by first moment and second moment methods

IV. Randomized algorithmic techniques (remainder of the semester)
  1. Randomized local search: Schoening's algorithm for SAT and variations
  2. Random walks on the line, gambler's ruin
  3. More on random walks and applications: graph connectivity
  4. Primality testing (guest lecture)  
  5. Balls into bins: The power of two choices (guest lecture)
  6. Approximation by randomized rounding of LPs. Example: MAXSAT (guest lecture)  
  7. Applications of random permutations: selecting the second
  8. Applications of random permutations: T. Chan's randomized optimization technique (examples: closest pair of points, smallest covering square)
  9. Distributed algorithm: leader election