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] ✍️ [Solutions]
-
Chapter 8: Streaming and Sketching I 📝 [Lecture notes 🚧] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 9: Streaming and Sketching II 📝 [Lecture notes 🚧] 🧑🏫 [Slides] ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 10: Linear Programming and Randomised Rounding 📝 [Lecture notes] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 11: Learning and testing probability distributions 📝 [Lecture notes] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
-
Chapter 12: Learning from Experts 📝 [Lecture notes] 🧑🏫 [Slides] (annotated) ✍️ [Tutorial] ✍️ [Solutions]
Two of the lecture note chapters (Chapters 8 and 9, indicated by a construction sign 🚧) are still incomplete: they will be updated in the future, before the next iteration of the course in 2025.
Feedback and suggestions welcome. The LaTeX source for the lecture notes, as well as some of the accompanying material, is available on GitHub under a CC BY-NC-ND 4.0 license.
