| Lecturer | Prof. Dr. Thomas Erlebach, ETZ G78.1 |
| Language | English |
| Type | 2V+2U (two hours lecture and two hours exercises per week) |
| Lecture | Monday 10-12h, ETZ F91 |
| Exercises | Friday 13-15h, ETZ E7 Tutors: Sai Anand, Alexander Hall, Matus Mihalak |
| Outline | The course will give an introduction to the competitive
analysis of online algorithms. Online algorithms must decide
how to act on incoming pieces of information without any
knowledge of future inputs. Online problems occur, for
example, in caching and paging (which cache block should be
evicted when the cache is full?), in scheduling and load
balancing (which job should be executed next and on which
machine?), in call admission control and routing (should a
newly requested connection be admitted into the network and
along which path should it be routed?), and in robot
navigation (which strategy should a robot use to explore an
unknown environment?). In the framework of
competitive analysis, the solution computed by the algorithm
is compared with the best possible solution that could have
been computed with unlimited computational power and complete
advance knowledge of the whole input sequence.
In the course, we will discuss various techniques for the design and analysis of online algorithms and apply them to problems arising in applications such as paging, real-time scheduling, load balancing, and routing and call admission control. |
| Prerequisites | Basic knowledge of graph theory and algorithms, combinatorics, and probability theory. |
| Reference | Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, 1998. |
| Monday (Lecture, ETZ F91, 10-12) | Friday (Exercises, ETZ E7, 13-15) | |
|---|---|---|
| Week 1 | 29.3.: Lecture 1, Problem Set 1 handed out | 2.4.: Discussion of Problem Set 1 (Sai) Solutions to Problem Set 1 |
| Week 2 | 5.4.: Lecture 2, Problem Set 2 handed out | 9.4.: ----- EASTER BREAK ----- |
| Week 3 | 12.4.: ----- EASTER BREAK ----- | 16.4.: Discussion of Problem Set 2 (Sai), Solutions to Problem Set 2 , Problem Set 3 handed out |
| Week 4 | 19.4.: Lecture 3 | 23.4.: Discussion of Problem Set 3 (Sai), Solutions to Problem Set 3 , Problem Set 4 handed out |
| Week 5 | 26.4.: Lecture 4 | 30.4.: Discussion of Problem Set 4 (Sai), Solutions to Problem Set 4 , Problem Set 5 handed out |
| Week 6 | 3.5.: Lecture 5 | 7.5.: Discussion of Problem Set 5 (Alex), Problem Set 6 handed out |
| Week 7 | 10.5.: Lecture 6 | 14.5.: Discussion of Problem Set 6 (Alex), Problem Set 7 handed out |
| Week 8 | 17.5.: Lecture 7 | 21.5.: ----- ASCENSION BREAK ----- |
| Week 9 | 24.5.: Lecture 8 | 28.5.: Discussion of Problem Set 7 (Matus), Problem Set 8 handed out |
| Week 10 | 31.5.: ----- PENTECOST BREAK ----- | 4.6.: Discussion of Problem Set 8 (Alex), Problem Set 9 handed out |
| Week 11 | 7.6.: Lecture 9 | 11.6.: Discussion of Problem Set 9 (Matus), Problem Set 10 handed out |
| Week 12 | 14.6.: Lecture 10 | 18.6.: Discussion of Problem Set 10 (Alex), Problem Set 11 handed out |
| Week 13 | 21.6.: Lecture 11 | 25.6.: Discussion of Problem Set 11 (Matus), Problem Set 12 handed out |
| Week 14 | 28.6.: Lecture 12 | 2.7.: Discussion of Problem Set 12 (Matus) |