The lectures and the tutorials take place at 8am on Tuesday and Wednesday (starting on September 26) in the lecture rooms A217 and A218, respectively. Please note that (in order to have a smooth flow of the presentation of the material) both slots will be lectures or both slots will be tutorials in some of the weeks.
More detailed information on the course can be found at the course webpage in the university information system..
Materials for the course can also be found in the university information system. (authentification required).
The exam will be an oral in person exam, and can be taken on Friday January 5, Friday January 26, Wednesday February 7 and Thursday February 15.
A brief summary of the topics covered during the lectures will be posted here.
| Date | Lecture content |
|---|---|
| 26/9/2023 | Basic probability concepts, linearity of expectation, independent events, conditional probability, analysis of the QuickSort algorithm, probabilistic algorithm for MINCUT, Las Vegas vs. Monte Carlo algorithms, geometric distribution | 27/9/2023 | Union Bound, Boole-Bonferroni Bounds, Markov's Inequality, Chebyshev's Inequality, Coupon Collector Problem | 10/10/2023 | 2-universal families of hash functions, hashing in the dynamic setting, perfect hashing in the static setting | 24/10/2023 | Chernoff's Bound (statement only), probabilistic complexity classes (ZPP, RP, BPP and PP), BPP⊆P/poly, 2-approximation algorithm for MAXCUT, derandomization by conditional expectation | 31/10/2023 | Probabilistic constructions - high-chromatic graphs with high girth, locally sparse graphs without large edge-cuts | 7/11/2023 | Discrete Markov chains, irreducibility, aperiodicity, uniquess of stationary distribution, convergence to stationary distribution | 8/11/2023 | Random walks on graphs, estimates on expected hitting times and expected cover time | 14/11/2023 | Yao's Principle and example of its application, Freivalds' Algorithm, Schwartz-Zippel Polynomial Identity Testing | 28/11/2023 | Primality testing - properties of primes and integers, BPP algorithm for primality test | 29/11/2023 | Miller–Rabin primality test, Seidel's linear programming algorithm | 12/12/2023 | fully polynomial-time randomized approximation scheme for the number of perfect matchings in bipartite graphs | 13/12/2023 | Luby's Maximal Independent Set Algorithm |