Randomised Algorithms

If you have any corrections or questions about the slides, please send me an email (tms41).

Complete Material

Lecture 1-12 (Handout, without animations, 1up) PDF

Lecture 1-12 (Handout, without animations, 4up) PDF

Lecture 1-12 (Slides, 1up) PDF

Material by Lectures

Lecture 1 (Introduction) PDF

References: Mitzenmacher, Upfal

Lecture 2 (Concentration Inequalities, Application to Balls-into-Bins) PDF

References: Mitzenmacher, Upfal (Chapter 4)

Lecture 3 (Concentration Inequalities, Application to Quick-Sort, Extensions) PDF

References: Mitzenmacher, Upfal (Chapter 4)

Lecture 4 (Markov Chains and Mixing Times) PDF

References: Mitzenmacher, Upfal (Chapter 7, 11, 12)

Lecture 5 (Random Walks, Hitting Times and A Randomised Algorithm for 2-SAT) PDF

References: Mitzenmacher, Upfal (Chapter 7); Levin, Wilmer, Peres

Lecture 6 (Linear Programming: Introduction) PDF

References: Cormen, Leiserson, Rivest, Stein (Chapter 29)

Lecture 7 (Linear Programming:Simplex Algorithm) PDF

References:

Cormen, Leiserson, Rivest, Stein (Chapter 29)

Tim Roughgarden, Beyond the Worst-Case Analysis of Algorithms (Chapter 1.2.1), Cambridge University Press, 2020.

Lecture 8 will be an interactive demo of how to solve a TSP instance using Linear Programming PDF

References:

Vasek Chvatal, William J. Cook, George B. Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson. Solution of a Large-Scale Traveling-Salesman Problem, 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 7-28, 2010.

G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson, Solution of a Large-Scale Traveling-Salesman Problem, Operation Research 2:393-410, 1954.

Lecture 9 (Approximation Algorithms: MAX-k-CNF and Vertex-Cover) PDF

References: Cormen, Leiserson, Rivest, Stein (Chapter 35)

Lecture 10 (Approximation Algorithms: Set-Cover and MAX-CNF) PDF

References: Cormen, Leiserson, Rivest, Stein (Chapter 35)

Lecture 11 (Spectral Graph Theory) PDF

References: Trevisan ''Lecture Notes on Graph Partitioning, Expanders and Spectral Methods''

Lecture 12 (Spectral Clustering) PDF

References: Trevisan ''Lecture Notes on Graph Partitioning, Expanders and Spectral Methods''

Corrections and Additions

1. Lecture 2, slide 1: Added one slide with remarks on the MAX-CUT problem
2. Lecture 2, slide 6: The condition delta > 0 should be replaced by 0 < delta < 1
3. Lecture 2, slide 12: log(4/e) should be log(e/4) (the rest of the argument remains unchanged)
4. Lecture 4, slide 9: first sentence should be ``irreducible if for every pair of states x,y there is k such that P^k(x,y) > 0''
5. Lecture 4, slide 18: Added one slide with further remarks on the definition of Mixing Time
6. Lecture 4, slide 27: The range of t should be 0,1,2... and not 1,2,..
7. Lecture 5, slides 20,21: time should be replaced by steps, since the runtime analysis counts the number of iterations of the repeat-loop and not the total time complexity (thanks to Dimitrios Los)
8. Lecture 7, slide 13.1: terminates if all coefficients in the objective function are ``negative''; it should be ``...are non-positive''. Also ``picks enterring variable x_e with negative coefficient'' should be ``with positive coefficient''.
9. Lectuer 12, slide 12: L_{u,v} = w_{u,v} / sqrt( d_u * d_v) should be L_{u,v} = -w_{u,v} / sqrt( d_u * d_v)

References

1. 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
2. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011 PDF
3. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2nd edition.
4. David Asher Levin, Elizabeth Wilmer, Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, 2009 PDF

Exercise Questions

• PDF