Randomised Algorithms 2017

Lecturers: Leen Stougie, Vrije Universiteit and CWI Amsterdam.
E-mail: stougie@cwi.nl or l.stougie@vu.nl

and

René Sitters, Vrije Universiteit and CWI Amsterdam.
E-mail: r.a.sitters@vu.nl


Course materials

Most parts of the course can be found in the book R. Motwani, P. Raghavan, Randomized Algorithms Cambridge University Press, 1995. Extra literature will be provided.


Examination

The examination is a take home exam, which students are to make alone or in groups of at most 2 with an exceptional group of 3 (by special request). The exercises have to be handed in by June 1, 2017, in order to be evaluated before the end of June 2017. Any later handing in will be evaluated at some undetermined later date. Please send a pdf-file with the work-outs to any of the two above e-mail addresses or handwritten versions by ordinary mail to Leen Stougie/Rene Sitters, Operations Research, Faculty of Economics and Business Administration, Vrije Universiteit, De Boelelaan 1105, 1081 HV Amsterdam.

Exercises: The exercises of the first 4 weeks will be mostly from the Book [MR]:

Be aware that the book contains Exercises (in the text of the chapters) and Problems (at the end of the chapters). The lists with your assignments shows exactly which of the two I mean. Open Problems are problems for which I do not yet have a solution in my solution manual. you don't need to make them. But if you do, then any such an open problem may replace two ordinary problems/exercises of your own choice.



Course week by week (at present this is a tentative list based on last time's course, it will be updated every week)

  • Week 1: Introduction. [MR] Chapter 1
  • Week 2: Game trees and On-line Scheduling. [MR] Chapters 2 and 13 (Section 13.1 and 13.3) + two papers in on-line scheduling (see my lecture notes below)
  • Week 3: The Coupon Collector's Problem and Stable Marriages [MR] Chapter 3 and Randomized Rounding and Global Wiring [MR] Chapter 4
  • Week 4: Randomized Rounding and Set Balancing, Derandomisation [MR] Chapter 4 and the Probabilistic Method and Maximum Satisfiability. [MR] Chapter 5
  • From here on Rene Sitters takes over. For the week-by-week continuation of the course, you are invited to go to Rene's website.


    This page has been made by Leen Stougie, and updated last on March 22, 2017.