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)
-
The lecture notes I made for myself for teaching can be found in Applications of Yao's Minimax Principle
- Exercises Week 2: From Chapter 2 in [MR] Problems 2.2, 2.3, 2.8; From the Lecture notes the Exercise on On-line Scheduling at the end of the notes
Week 3: The Coupon Collector's Problem and Stable Marriages [MR] Chapter 3 and Randomized Rounding and Global Wiring [MR] Chapter 4
-
The lecture notes I made for myself for teaching can be found in
High probability and Chernoff Bounds
- Exercises Week 3: From Chapter 3 in [MR]:
Exercises 3.5 and 3.6 and
Problems 3.13 to be proven $1-e^{-2e^{-c}$.
Open Problems are 3.11, 3.15
Week 4: Randomized Rounding and Set Balancing, Derandomisation [MR] Chapter 4 and the Probabilistic Method and Maximum Satisfiability. [MR] Chapter 5
-
The lecture notes I made for myself for teaching can be found in Derandomization, Randomised LP-rounding.
- Exercises Week 4: From Chapter 4 in [MR]:
Exercise 4.7, Problem 4.15 + the Exercise on Set Balancing in the Lecture Notes;
From Chapter 5 in [MR]: Problems 5.3, 5.11;
Open Problems 5.7, 5.10, 5.14
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.