Clément Canonne
Content for the COMP4270 and COMP5270 Course on “Randomised and Advanced Algorithms” at the University of Sydney
This page will be updated weekly, as the content is written and uploaded. 12 lectures (one chapter per lecture), and one review lecture. Slides will come later.
Each chapter is the basis for a two-hour lecture, and the class is aimed at last-year undergrads and masters of computer science students, without required previous exposure to advanced algorithms. It is not, by design, meant to be comprehensive. Some very nice algorithms will be missing; many important ideas may not make the cut.
-
Chapter 1: Randomness, Probability, and Algorithms 📝 [Lecture notes] 🎞️ [Video] 🧑🏫 [Slides] ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 2: Concentration Bounds, and Tricks 📝 [Lecture notes] 🧑🏫 [Slides] ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 3: Balls in Bins 📝 [Lecture notes] 🧑🏫 [Slides] (quite bare) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 4: Derandomisation 📝 [Lecture notes] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 5: Graph algorithms 📝 [Lecture notes] 🧑🏫 [Slides] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 6: Hashing and Friends 📝 [Lecture notes] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 7: Nearest Neighbours and dimensionality reduction 📝 [Lecture notes] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial]
Feedback and suggestions welcome. The LaTeX source for the lecture notes (up to Chapter 5 so far), as well as some of the accompanying material, is available on GitHub under a CC BY-NC-ND 4.0 license.
