Teaching

Randomized and Online Algorithms

ModuleBMINF014
ECTS6
InstructorPD Dr. Alexander Souza
Contact alexander@algomia.com
UZH Linkhere
OLAT Linkhere
Introductory Slideshere
Zoom MeetingAnnounced via OLAT
WeekdaysThursday 8:15-9:45
Friday 8:15-9:45
Exercisesbiweekly, see schedule below
Start17.9.2020
End18.12.2020
Exam14./15.1.2021
AdmissionHalf of the exercise problems must be worked on (serious attempt) for admission to the exam.

Description

This lecture covers the design and analysis of "randomized" as well as "online" algorithms.

A "randomized algorithm" is allowed to use randomness in its decision-making. In contrast, an "online algorithm" must make decisions "on the fly" before all of the information is available, and thus must be able to decide "under uncertainty."

The analysis will also be an important and integral part. That is, we will not only state the properties of an algorithm, e.g. its correctness or running time, but also prove them mathematically.

In particular, we plan to treat the following topics:

  1. Linearity of Expectation
  2. Bounds on Probabilities
  3. Markov Chains
  4. Randomized Rounding
  5. Probabilistic Method
  6. Load Balancing
  7. Bin Packing
  8. List Update

Schedule

17.9.Session 01Randomized Algorithms: Introduction
18.9.Session 02Model of Computation
24.9.Session 03Linearity of Expectation
25.9.Session 04Linearity of Expectation
1.10.Session 05Bounds on Probabilities
2.10.Session 06Exercise 1
8.10.Session 07Bounds on Probabilities
9.10.Session 08Bounds on Probabilities
15.10.Session 09Markov Chains
16.10.Session 10Exercise 2
22.10.Session 11Markov Chains
23.10.Session 12Markov Chains
29.10.Session 13Markov Chains
30.10.Session 14Exercise 3
5.11.Session 15Markov Chains
6.11.Session 16Randomized Rounding
12.11.Session 17Randomized Rounding
13.11.Session 18Exercise 4
19.11.Session 19Randomized Rounding
20.11.Session 20Randomized Rounding
26.11.Session 21Probabilistic Method
27.11.Session 22Exercise 5
3.12.Session 23Probabilistic Method
4.12.Session 24Online Algorithms: Introduction
10.12.Session 25Load Balancing
11.12.Session 26Exercise 6
17.12.Session 27Bin Packing
18.12.Session 28List Update

Literature