Lectures and office hours will be held on zoom to start the semester at the following link:

https://purdue-edu.zoom.us/j/94663689769

Piazza

Syllabus, policies, and procedures

Similar courses elsewhere

Randomized Algorithms.
David Karger (MIT).

Randomized Algorithms.
Sariel Har-Peled (UIUC).

Randomness and Computation.
Alistair Sinclair (Berkeley).

Algorithms for Big Data.
Jelani Nelson (Harvard).

Algorithms for Big Data.
Chandra Chekuri (UIUC).

Randomized Algorithms.
Avrim Blum and Anupam Gupta (CMU).

Advanced algorithms.
Ankur Moitra (MIT).

Pseudorandomness.
Salil Vadhan (Harvard).

Randomized Algorithms and Probabilistic Analysis.
Greg Valiant (Stanford).

Textbook: Randomized Algorithms, by Motwani and Raghavan

Other recommended texts include Probability and Computing, by Mitzenmacher and Upfal; and The Probabilistic Method, by Alon and Spencer

Key dates

Midterm and final are both TBD

Calendar

TuesdayThursday
8/25Heavy hitters8/27Linear probing

Homework A

Notes on basic probability by Chandra Chekuri; Cormode and Muthukrishnan (2005); Notes from Fall '19 randomized algorithms class; Notes by Moses Charikar; Video lecture by Ankur Moitra; Video lecture by Jelani Nelson; Notes by Chandra Chekuri; Notes from Spring '20 algorithms class on universal hashing

Homework B

Handwritten notes from lecture; Knuth (1963); Pagh, Pagh, and Ruzic (2006); Notes by Mikkel Thorup; Video from Spring 2020; Video by Jelani

9/1Distinct elements9/3Dimensionality reduction

Homework C

Handwritten notes from class; Flajolet, Martin (1985); Alon, Matias, Szegedy (1996); Notes by Chandra Chekuri; Notes by Moses Charikar; Notes by Jelani

Homework D

Handwritten notes from class; Chapter 2 of book by Blum, Hopcroft, Kannan (2018); Notes by Sariel Har-Peled; Video by Ankur Moitra; Cohen, Jayram, Nelson (2018); Indyk (2001)

9/8Locality Sensitive Hashing9/10Min cuts and sparsification

Homework E

Handwritten notes from class; Indyk, Motwani (1998); Charikar (2004); Har-Peled, Indyk, Motwani (2012); Andoni and Indyk (2008 survey); Slides by Piotr Indyk; Slides by Chandra Chekuri; Notes by Sanjoy Dasgupta; Notes by Ankur Moitra

Homework F

Handwritten notes from class; Handwritten notes from Fall 2019; Nagamochi and Ibaraki (1992); Karger (1993); Karger and Stein (1996); Karger's thesis (1995)

9/15Sparsification9/17MST

Homework G

Benczur and Karger (2015); Fung, Hariharan, Harvey, Panigrahi (2019)

Homework H

Karger, Klein, and Tarjan (1995); Dixon, Rauch, Tarjan (1992); King (1997); Buchsbaum et al.