Teaching Material: Master (2022-..)

Master MPRI Course 2.15: Analysis of algorithms (AofA)

Lectures 14 to 17: Analysis of Probabilistic algorithms

Content: Lecture 14: Probabilistic Toolbox (Events, Conditioning, Deviations...) Exercise sheet Lecture 15: The Probabilistic Method (1st and 2d moment method) Exercise sheet Lecture 16: Balls in bins (Collisions, Coupon Collector, Random allocations,...) Exercise sheet Lecture 17: Data streams algorithms (Morris' Algorithm, MinCount, CVM's algorithm...) Exercise sheet Material: Online review of the course (updated after each class) Probability Reminder Training session: Exercise sheet Final exam (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)