Master MPRI Course 2.15: Analysis of algorithms (AofA)

Lectures 14 to 17: Analysis of Probabilistic algorithms

Detailed content of the course (with references) Probability Reminder Exercise sheet #1: Probabilistic Toolbox (Events, Conditioning, Deviations...) Exercise sheet #2: The Probabilistic Method (1st and 2d moment method) Exercise sheet #3: Balls in bins (Collisions, Coupon Collector, Random allocations,...) Exercise sheet #4: Data streams algorithms (Morris' Algorithm, MinCount, CVM's algorithm...) Exercise sheet #5 Training session (Triangles in \( \mathcal{G}(n,p)\), Independent sets in graphs...) Final exam (February 2025) (Diameter in Erdos-Rényi's random graph)

MasterClass (Nancy, 2022): Mini-course on random permutations

Lecture notes: "Random uniform permutations" Link: online simulations (python)