Randomised Algorithms

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

Complete Material

Lecture 1-12 (Presentation, 1up) PDF

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

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

Material by Lectures

Lecture 1 (Introduction) Presentation - Handout (1up) - Handout (4up)

References: Mitzenmacher, Upfal (Chapter 2.4.1, Chapter 6.2.1)

Lecture 2 (Concentration Inequalities, Application to Balls-into-Bins) Presentation - Handout (1up) - Handout (4up)

References: Mitzenmacher, Upfal (Chapter 4)

Lecture 3 (Concentration Inequalities, Application to Quick-Sort, Extensions) Presentation - Handout (1up) - Handout (4up)

References: Mitzenmacher, Upfal (Chapter 4)

Lecture 4 (Markov Chains and Mixing Times) Presentation - Handout (1up) - Handout (4up)

Slides 22-26 were not covered in Lecture 4, but will be covered in Lecture 5
References: Mitzenmacher, Upfal (Chapter 7, 10, 11, 12)

Lecture 5 (Random Walks, Hitting Times and A Randomised Algorithm for 2-SAT) Presentation - Handout (1up) - Handout (4up)

References:

Mitzenmacher, Upfal (Chapter 7)

Levin, Wilmer, Peres (Chapter 2.3, Chapter 10)

Paper that analyses time to visit all vertices on a two-dimensional torus: ``Cover Times for Brownian Motion and Random Walks in Two Dimensions'', Amir Dembo, Yuval Peres, Jay Rosen and Ofer Zeitouni. Annals of Mathematics, 160 (2004), pages 433-464.

PDF

Lecture 6 (Linear Programming: Introduction) Presentation - Handout (1up) - Handout (4up)

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

Lecture 7 (Linear Programming: Simplex Algorithm) Presentation - Handout (1up) - Handout (4up)

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 (Demo how to solve a TSP instance using Linear Programming) Presentation - Handout (1up) - Handout (4up)

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) Presentation - Handout (1up) - Handout (4up)

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

Lecture 10 (Approximation Algorithms: Set-Cover and MAX-CNF) Presentation - Handout (1up) - Handout (4up)

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

Lecture 11 (Spectral Graph Theory) Presentation - Handout (1up) - Handout (4up)

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

Lecture 12 (Spectral Clustering) Presentation - Handout (1up) - Handout (4up)

Correction: On slide 10, Physical Interpretation, the first equation (right hand side), there is a sum over the edges from u to v missing.
References: Trevisan ''Lecture Notes on Graph Partitioning, Expanders and Spectral Methods''

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

1. Recommended Questions for Supervision 1
1. Lec 1:
• Question 1 (Coupon-Collecting)
• Question 5 (MAX-CUT and Chebyshev)
2. Lec 2/3:
• Question 3 (Derivation of Chernoff Bounds)
• Question 6 (QuickSort)
• Question 9 (MAX-CUT and Method of Bounded Differences)
3. Lec 4/5:
• Question 4 (Markov Chain modelling Waiting Time for Bus)
• Question 9 (Stationary Distribution)


2. Recommended Questions for Supervision 2
1. Lec 4/5:
• Question 13 (Stationary Distribution)
• Question 16 (Hitting Time for Paths)
• Question 17 (optional/difficult; closer look at the 2-SAT algorithm analysis)
2. Lec 6/7:
• Question 3 (easy warm-up question)
• Question 5 (Convexity of feasible region)
• Question 12 (Example of SIMPLEX and INITIALIZE-SIMPLEX)
3. Lec 9/10:
• Question 1 (easy; Guessing Approach for MAX-SAT)
• Question 2 (Derandomisation)
• Question 10 (randomised rounding for SET-COVER)
3. Recommended Questions for Supervision 3
1. Lec 9/10:
• Question 12 (Hybrid algorithm for MAX-SAT)
2. Lec 11/12:
• Question 1 (relating spectrum of Laplacian Matrix and Adjacency Matrix)
• Question 2 (conductance of complete graph)
• Question 5 (eigenvalues of transition matrix of lazy random walks)
• Question 9 (spectrum of complete graph)
• Question 11 (easy; applying Spectral Clustering)
• Question 13 (largest eigenvalue of Laplacian Matrix)