On-Line Algorithms


Announcement:

The Tuesday times have been moved from 10:15-12 to 12:15-14. All of these new times will be in U89. The Wednesday times are unchanged.

Description

A course description.

The textbook:

Online Computation and Competitive Analysis, by Borodin and El-Yaniv. There will also be notes.
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.

Exam

  1. The exam questions from 2003 are here (and also in PDF).
  2. The exam questions from 2004 are here (and also in PDF).
  3. The exam questions for 2005 were the same as for 2004.

Weekly notes

    Lecture 1.ps also in PDF.
    Lecture 2.ps also in PDF.
    Lecture 3.ps also in PDF.
    Lecture 4.ps also in PDF.
    Lecture 5.ps also in PDF.
    Lecture 6.ps also in PDF.
    Lecture 7.ps also in PDF.
    Lecture 8.ps also in PDF.
    Lecture 9.ps also in PDF.
    Lecture 10.ps also in PDF.
    Lecture 11.ps also in PDF.
    Lecture 12.ps also in PDF.
    Lecture 13.ps also in PDF.
    Lecture 14.ps also in PDF.
    Lecture 15.ps also in PDF.

Miscellaneous

  1. Article on the relative worst order ratio as applied to paging.
  2. Article introducing the relative worst order ratio.
  3. Older version of the paper.
  4. Susanne Albers' lecture notes in BRICS lecture series, number LS-96-2.
  5. Michel Goemans has course notes on on-line algorithms on his home page.

   
IMADA HOME | SDU HOME | Previous page |
Last modified: Wed May 17 15:36:06 CEST 2006 - Joan Boyar <joan@imada.sdu.dk>