Course pages 2018–19
Probability and Computation
*** Mock Exam *** (solutions)
Lecture notes
- Lecture 1: Introduction (slides)
- Lecture 2: Markov Chains (slides)
- Lecture 3: Coupling and Convergence (slides)
- Lecture 4: Card Shuffling and Covertime (slides, print)
- Lecture 5: Concentration Inequalities (slides)
- Lecture 6: Concentration Inequalities - Introduction to Martingales (slides)
- Lecture 7: Martingales and Concentration (slides)
- Lecture 8: The Optional Stopping Theorem (slides)
- Lecture 9: Linear algebra review and Markov chains (slides)
- Lecture 10: Mixing time and eigenvalues (slides)
- Lecture 11: Graph clustering and random walks (slides, example)
- Lecture 12: Graph clustering and beyond (slides)
- Lecture 13-14: Sublinear-Time Algorithms (slides, print)
- Lecture 15: Dimensionality Reduction (slides)
Problem sheets
- Problem sheet 1 (Lectures 1-3)
- Problem sheet 2 (Lectures 4-5)
- Problem sheet 3 (Lectures 6-7)
- Problem sheet 4 (Lectures 8-9)
- Problem sheet 5 (Lectures 10-11)
- Problem sheet 6 (Lectures 11-16) with solutions
Solutions to exercises
- Homework Assessment
- 24th of January problem class
- Problem sheet 1
- Problem sheet 2
- Problem sheet 3
- Problem sheet 4
- Problem sheet 5