DM205: On-Line Algorithms

Announcement:

There will be no class on Wednesday, March 16, but we will meet at the usual time on Thursday, March 27. Come with questions.

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.

A required article:

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).

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) are here.
  4. The exam questions, along with a list of required reading material, for 2014 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

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.

   
IMADA HOME | SDU HOME | Previous page |
Last modified: Mon Mar 24 16:10:05 CET 2014 - Joan Boyar <joan@imada.sdu.dk> 		   

 

   Data protection at SDU ▪ Databeskyttelse på SDU