Course RA: Randomized Algorithms

Time:

Monday 11.00 - 12.45 (March 6 - April 3 and April 17 - May 15)

Location:

All LNMB courses can be attended on the Campus Utrecht Science Park. The lecture room for the first week is different from all other weeks:

March 6: Buys Ballot building - lecture room 161
March 13, 20, 27; April 3, 17, 24; May 1, 8, 15: Minnaert building - lecture room 2.02

Note that there's no lecture on April 10 (Easter)

Lecturer:

Dr. R.A. Sitters (CWI, VU Amsterdam), Dr. L. Rohwedder (Maastricht University).

Course description:
The topics are:
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 Lovasz Local lemma.

Prerequisites:
Elementary knowledge of probability theory.

Examination:
Take home problems.

Address of the lecturers:

Dr.ir. R.A. Sitters
Department of Econometrics and Operations Research
Faculty of Economics & Business Administration, VU University Amsterdam,
De Boelelaan 1105, 1081 HV Amsterdam
Phone: 020 - 5989391
E-mail: rsitters@feweb.vu.nl

Dr. L. Rohwedder
Quantitative Economics, School of Business and Economics, Maastricht University