Course RA: Randomized Algorithms

Time:	Monday 15.15 – 17.00 (February 17 – May 12 with the exceptions of 10 March, 21 April, 28 April, 5 May)
Location:	All LNMB courses take place on the Campus Utrecht Science Park. Room HFG 611, Hans-Freudenthal building, Budapestlaan 6, 3584 CD Utrecht
Lecturers:	Dr. R.A. Sitters (CWI, VU Amsterdam), Dr. ir. T. Oosterwijk (Vrije Universiteit Amsterdam)

Course description

Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. This course will explore examples from a variety of settings and problem areas such as graph algorithms, algorithms in algebra, approximate counting, probabilistically checkable proofs, algorithms for big data, and matrix algorithms. Topics also include an introduction to tools from probability theory, including martingales, Chernoff bounds and the Lovász Local Lemma.

A tentative list of topics is:

Quicksort
Fingerprinting technique
Online algorithms
Chernoff bounds
Derandomization
Randomized rounding
Semidefinite programming
Approximate counting
Probabilistic method
Lovász Local Lemma
PTAS for Euclidean TSP
Probabilistically checkable proofs
Various graph algorithms

Prerequisites

Elementary knowledge of probability theory.

Examination:

Take home problems.

Address of the lecturers

Dr. ir. R.A. Sitters
Department of Operations Analytics
School of Business and Economics, Vrije Universiteit Amsterdam
De Boelelaan 1105, 1081 HV Amsterdam
Phone: 020 - 5989391
E-mail: r.a.sitters@vu.nl

Dr. ir. T. Oosterwijk
Department of Operations Analytics
School of Business and Economics, Vrije Universiteit Amsterdam
De Boelelaan 1105
1081 HV, Amsterdam
Email: t.oosterwijk@vu.nl