DM860: On-Line Algorithms


Announcements:

Assignments:

  1. Assignment 1 is due at 10:15 on March 19.
  2. Assignment 2 is due at 10:15 on April 23.
  3. Assignment 3 is due at 10:15 on May 21.

The textbook:

Online Computation and Competitive Analysis, by Borodin and El-Yaniv.
There is a homepage for the textbook, including errata list.
Further errata found by students who took this course earlier.
Further errata found by students who took this course in 2004.

Required articles:

Reading list for the 2017 and 2019 exam

The reading list for 2017 and 2019 is here.

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.
  6. The exam questions for 2019 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 (One lecture note got skipped.).
  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.

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 related to lectures on the relative worst order ratio applied to paging.
  4. Slides related to 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>
   

 


   Data protection at SDUDatabeskyttelse på SDU