DM860: On-Line Algorithms

Announcements:

• The third (last) assignment has been graded. The redo is due on June 6 at 12:15.
• The reading list and exam topics for 2017 are now available on this course homepage.
• The exam will be on June 23.

Assignments:

1. Assignment 1.pdf: Due 12:15 on March 15. Redo due 12:15 on March 29.
2. Assignment 2.pdf: Due 12:15 on April 19. Redo due 12:15 on May 2.
3. Assignment 3.pdf: Due 12:15 on May 26. Redo due 12:15 on June 6.

The textbook:

Required articles:

• The Relative Worst Order Ratio Applied to Paging.
  Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
  Journal of Computer and System Sciences, 73(5): 818-843, 2007.
  The publication is available from ScienceDirect (students can obtain this publication at no cost by being logged in on an SDU computer).
• Online Bin Packing with Advice.
  Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
  Algorithmica, 74(1): 507-527, 2016.
  The publication is available from SpringerLink (students can obtain this publication at no cost by being logged in on an SDU computer).
• The Advice Complexity of a Class of Hard Online Problems.
  Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
  Theory of Computing Systems, First Online 2016.
  The publication is available from SpringerLink (students can obtain this publication at no cost by being logged in on an SDU computer).

Reading list for exam

Exam

1. The exam questions from 2003 for a semester version of the course are here (and also in PDF).
2. The exam questions from 2004 and 2005 for a semester version of the course are here (and also in PDF).
3. The exam questions for 2009 and 2010 (both spring and fall) for a 5 ECTS version of the course are here.
4. The exam questions, along with a list of required reading material, for 2014 for a 5 ECTS version of the course are here.
5. The exam questions for 2017 for a 10 ECTS version of the course are here.

Notes for Lectures, including problems for discussion sections

1. Lecture 1.pdf .
2. Lecture 2.pdf.
3. Lecture 3.pdf.
4. Lecture 4.pdf.
5. Lecture 5.pdf.
6. Lecture 6.pdf.
7. Lecture 7.pdf.
8. Lecture 8.pdf.
9. Lecture 9.pdf.
10. Lecture 10.pdf.
11. Lecture 11.pdf.
12. Lecture 12.pdf.
13. Lecture 13.pdf.
14. Lecture 14.pdf.
15. Lecture 15.pdf.
16. Lecture 16.pdf.
17. Lecture 17.pdf.
18. Lecture 18.pdf.
19. Lecture 19.pdf.

Additional references

1. Susanne Albers' lecture notes in BRICS lecture series, number LS-96-2.
2. Michel Goemans has course notes on on-line algorithms on his home page.
3. Slides presented in lectures on the relative worst order ratio applied to paging.
4. Slides presented in lectures on advice complexity.

IMADA HOME | SDU HOME | Previous page | Last modified: Mon May 29 15:14:13 CEST 2017 - Joan Boyar <joan@imada.sdu.dk>