DM205: On-line Algorithms (5 ECTS)

STADS: 15006201

Level
PhD course

Teaching period
The course is offered in the autumn semester.
Offered when needed.

Teacher responsible
Email: joan@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 3. + 4.kvartal

Prerequisites:
None

Academic preconditions:
Bachelor's degree. The content of DM508 Algorithms and Complexity should be known

Course introduction
A problem is "on-line" if a sequence of requests must be processed by making decisions for each request without knowing the succeeding ones. The decision made can have significant consequences for the ability to service the succeeding requests. Example problems of this nature are container packing, stock market investments, processor scheduling, paging/buffer problems, reorganization of symbol tables, reservation of bandwidth in networks, and seat reservations in trains. In this course, however, we focus primarily on the more computer science oriented problems. The purpose of the course is to give the participants knowledge of on-line problems and algorithms in general, and the most widely applicable problem classes in particular. The emphasis is on the analysis of the quality of these algorithms, along with the design techniques.

Expected learning outcome
After the course the students should be able to:

• perform a competitive analysis on an arbitrary on-line algorithm
• compare two arbitrary on-line algorithms using relative worst order analysis
• use techniques from the course to design deterministic and randomized on-line algorithms
• prove upper and lower bounds on the performance of on-line algorithms
• modify known on-line algorithms to special cases of known problems and to new problems
• design and analyze new on-line algorithms to solve problems which resemble problems from the course

Subject overview
Competitive analysis, relative worst order analysis, deterministic and randomized algorithms, upper and lower bounds, and a number of the most common concrete on-line problems.

Literature

• Meddeles ved kursets start.: .

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam. Danish 7 mark scale, external examiner.

Terms for re-exam according to the rules decided by the Study Board.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger, antal timer 21.
Eksaminatorietimer/opgaveregning, antal timer 21.
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.