Announcements
The oral examination will be held on Monday 23/9/2019, 12.00-13.00, at the office of prof. Sotiris Nikoletseas (PROKAT building).
From 2012, the course will focus on Randomized Algorithms (and applications of the Probabilistic Method to their design and analysis).
A Monte Carlo Minimum Cut Algorithm.
Las Vegas Algorithm for Closest Pair of Points in the Plane.
Occupancy, Moments and Deviations, Randomized Selection.
Two-point Sampling, Coupon Collector's Problem.
The Principle of Deferred Decisions. Chernoff Bounds.
Markov chains and random walks - cover times, 2-SAT algorithm.
Lovász Local Lemma - k-SAT algorithms.
Martingales - occupancy revisited.
The course will be based on the textbook “Randomized Algorithms”, by R. Motwani and P. Raghavan, Cambridge University Press (the CEID library maintains 10 copies of the book).
The oral examination material is the following:
The lecture slides
Random Walks on Graphs presentation. Optionally, you may read an additional material which may help you understand the presentation.
Lecture 1: A Monte Carlo Minimum Cut Algorithm
Lecture 2: Las Vegas Algorithm for Closest Pair of Points in the Plane
Lecture 3: Occupancy, Moments and Deviations
Lecture 4: Randomized Selection
Lecture 5: Two-point Sampling
Lecture 6: Coupon Collector's Problem
Lecture 7: The Principle of Deferred Decisions
Lecture 8: Chernoff Bounds
Lecture 9: Random Walks
Lecture 10: Markov Chains