Randomised Algorithms
Lecture Slides
- Lecture 1 (Introduction) PDF
- Lecture 2-3 (Concentration Inequalities and Chernoff Bounds) PDF References: Mitzenmacher, Upfal (Chapter 4)
- Lecture 4 (Markov Chains and Mixing Times) PDF References: Mitzenmacher, Upfal (Chapter 7, 11)
- Lecture 5 (Random Walks, Hitting Times and A Randomised Algorithm for 2-SAT) PDF References: Mitzenmacher, Upfal (Chapter 11); Levin, Wilmer, Peres
- Lecture 6-7 (Linear Programming and the Simplex Algorithm) PDF References: Cormen, Leiserson, Rivest, Stein (Chapter 29)
- Lecture 8 will be an interactive demo of how to solve a TSP instance using Linear Programming
- Lecture 9-10 (Randomised Approximation Algorithms) PDF References: Cormen, Leiserson, Rivest, Stein (Chapter 35)
- Lecture 11-12 (Spectral Graph Theory and Clustering) PDF References: Trevisan ``Lecture Notes on Graph Partitioning, Expanders and Spectral Methods'' PDF
- Lecture 13 (Streaming Algorithms) PDF References: Muthurkishnan ``Data Streams: Algorithms and Applications'' PDF
- Lecture 14 (Online Learning with Experts) PDF References: Understanding Machine Learning: From Theory to Algorithms (Chapter 21), Cambridge University Press
- Lecture 15 (Multi-Armed Bandits) PDF References: Lattimore, Szepesvari ``Bandit Algorithms'', Cambridge University Press PDF
Some of the animations (Lecture 5 and Lecture 11-12) may require a special PDF reader like Adobe Acrobat Reader.
If you have any questions or found errors in the slides / videos / exercise questions, please email me: [Javascript required]
Handout (compressed version of slides without lengthy animations)
Corrections
- 25. January: Lecture 4, slide 11: fixed definition of periodicity
- 27. January: Lecture 2/3, slide 30: fixed Quick-Sort Example (in the tree, there was a redundant node with a single "1", and thus the sum of comparison formula was also wrong).
- 23. February: Lecture 13, slide 15: It was wrongly claimed that with probability 1/2^r, we have rho(h(x))=r. Instead, it should be with probability 1/2^r, we have rho(h(x))>=r. Many thanks to Nav Leelarathna.
- 11. March: Lecture 15. Several minor typos fixed and explanations added.
- 5. April: Lecture 14, slide 19, 20 and 22: The factor sqrt(2) in the mistake bound should instead be 2. Many thanks to Nav Leelarathna.
References
- Cormen, T.H., Leiserson, C.D., Rivest, R.L. and Stein, C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN 978-0-262-53305-8
- David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011 PDF
- Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2nd edition.
- David Asher Levin, Elizabeth Wilmer, Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, 2009 PDF
Exercise Questions
- The questions discussed in the example classes are highlighted.
Example Classes
- Example Class 1 (3 February) Slides PDF or Handout PDF Exercise Questions: L1 Q1, L2/3 Q2,5 and 7.
- Example Class 2 (10 February) Handout PDF Exercise Questions: L4/5 Q2,4,6,12 and 14.
- Example Class 3 (17 February) Slides PDF or Handout PDF Demo on how we can use Linear Programming in order to solve an instance of the Travelling Salesman Problem
- Example Class 4 (24 February) Handout PDF Exercise Questions: L6/7 Q3,4 L9/10 Q2,5, L11/12 Q6
- Example Class 5 (10 March) Handout PDF Exercise Questions: L11/12 Q5, L13 Q1, L14 Q1, Q3, Q4
- All example classes will be recorded.
Link to the Program including Data Set and Visualisation: Link
Reference to the Article fom 1954: Dantzig, G., Fulkerson, R. and Johnson, S. (1954) Solution of a Large-Scale Traveling-Salesman Problem. Journal of the Operations Research Society of America, 2, 393- 410. Link