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

The animations in the presentations of Lecture 5 and 12 may only work with certain viewers (e.g., Adobe Acrobat Reader).

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)

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

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

Correction: On slide 15, in the Proposition it should be k < n (instead of k <= n). Thanks to the student for pointing that out!
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)

Correction: On slide 9, in the definition it should be x in C^n (instead of x in R^n). Thanks to the student for pointing that out!
Correction: On slide 15, in the definition of Courant-Fischer, the minimsation should be over any k-dimensional subspace. Thanks to a student for pointing that out!
References: Trevisan ''Lecture Notes on Graph Partitioning, Expanders and Spectral Methods''

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

Minor Correction: The drawing of the embedding (Slide 15) has been updated.
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:
• Exercise 1 (Coupon-Collecting)
• Exercise 5 (MAX-CUT and Chebyshev)
2. Lec 2/3:
• Exercise 3 (Derivation of Chernoff Bounds)
• Exercise 6 (QuickSort)
• Exercise 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 15 (optional; closer look at the 2-SAT algorithm analysis)
• Question 16 (Hitting Time for Paths)
2. Lec 6/7:
• Question 3,4 (easy warm-up questions)
• 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 3 (conductance of cycle)
• Question 5 (eigenvalues of transition matrix of lazy random walks)
• Question 9 (spectrum of complete graph)
• Question 11 (easy; Spectral Clustering)