Probability and Computing, Oxford 2018-19
Table of Contents
- Instructor
- Elias Koutsoupias
- Lectures
- Wednesday, 11:00 - 12:00 ( Weeks 1-8 ) LTB
- Friday, 12:00 - 13:00 ( Weeks 1-8 ) LTA
- Friday, 14:00 - 15:00 ( Weeks 1-4 ) LTA
- Classes
- Check Minerva
Hand in homework : Friday 2pm - Office hours
- Wednesday, 12:00 - 13:00, Room 363
This will be the main webpage of the course, which will be updated during the course with notes, homework etc. The standard page of the course contains past exams, overview, learning outcomes etc.
Visit the webpage of last year to see the topics and the material of the course. This year, we plan to cover the same material, but there will be some changes in the schedule and homework.
Lectures
These notes are incomplete and most likely contain inaccuracies, typos, and errors. It is strongly advised to study from the textbook. It is very useful to read notes from similar courses at other universities to get a more general perspective.
Lectures in html
- Lecture 1: A randomised algorithm for string equality
- Lecture 2: Min-cut contraction algorithm
- Lecture 3: The secretary problem and the prophet inequality
- Lecture 4: Linearity of expectations
- Lecture 5: Derandomisation
- Lecture 6: Further applications of linearity of expectations
- Lecture 7: Markov’s and Chebyshev’s inequalities
- Lecture 8: Chernoff bounds
- Lecture 9: Applications of Chernoff bounds
- Lecture 10: Martingales and stopping times
- Lecture 11: The Azuma-Hoeffding inequality
- Lecture 12: Applications of the Azuma-Hoeffding inequality
- Lecture 13: Markov chains, 2SAT, and 3SAT
- Lecture 14: Markov chains and random walks
- Lecture 15: The Monte Carlo method
- Lectures 16-17: Mixing time
- Lecture 18: Lovasz Local Lemma
- Lecture 19: Interactive proofs
- Lecture 20: Online algorithms - Paging
Lectures in pdf
- All lectures in one file (updated after every lecture)
Homework
Sources
Textbook
Michael Mitzenmacher and Eli Upfal. Probability and Computing