DM860: Online Algorithms

The Study Board for Science

Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340035102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master's level course approved as PhD course

STADS ID (UVA): N340035101
ECTS value: 10

Date of Approval: 09-05-2025


Duration: 1 semester

Version: Approved - active

Comment

The course was offered F21 and exam attempts for DM860 are offered: January 2022, first re-examination in March 2022 and 2nd re-examination in June 2022.

The course is offered as required and is not necessarily offered every year. Exam attempts for DMXXX are offered in accordance to the following plan, when the course is offered: Autumn (course Start september): ordinary Exam (January), first reexamination (March) and 2nd reexamination (June or August).

Entry requirements

A bachelor degree in computer science, mathematics, applied mathematics, mathematics-economy or comparable.

Academic preconditions

Students taking the course are expected to be able to use basic probability, and analyze algorithms.

The course builds on the knowledge acquired in the courses DM549 Discrete Methods for Computer Science or MM537 Introduction to Mathematical Methods, DM551 Algorithms and Probability or MM541 Combinatorial Mathematics, DM507 Algorithms and Data Structures, and DM553 Complexity and Computability.

The course gives an academic basis for writing a Master's thesis in online algorithms.

Course introduction

The aim of the course is to enable the student to understand and work with fundamental concepts in online problems and algorithms, especially the design and analysis of online algorithms. 

The purpose of this course is to study online problems and algorithms. A problem is online if requests arrive sequentially and the online algorithm must make an irrevocable decision regarding each request without seeing any future requests. Examples of such problems include packing of containers, investment in the stock market, scheduling jobs on processors, reorganization of symbol tables, reservation of seats in a train, or reservation of bandwidth in a network. The concentration will be on analysis and design techniques.

Expected learning outcome

The learning objectives of the course is that the student demonstrates the ability to:
  • Perform a competitive analysis on an arbitrary online algorithm 
  • Compare two arbitrary online algorithms using relative worst order analysis
  • Use techniques from the course to design and analyze deterministic and randomized online algorithms, plus online algorithms with advice 
  • Prove upper and lower bounds on the performance of on-line algorithms
  • Modify known online algorithms to special cases of known problems and to new problems 
  • Design and analyze new online algorithms to solve problems which resemble problems from the course

Content

The following main topics are contained in the course:
  • Competitive analysis
  • Other performance quality measures, such as relative worst order analysis
  • Deterministic and randomized algorithms, plus online algorithms with advice
  • Upper and lower bounds
  • A number of the most common concrete online problems, such as paging and list access

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Autumn and January

Tests

Portfolio

EKA

N340035102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card - Name

Language

Normally, the same as teaching language

Duration

Oral exam - 30 minutes + 30 minutes preparation

Examination aids

All common aids allowed. Only notes prepared during the preparation time may be brought to the exam itself.

ECTS value

10

Additional information

Portfolio consisting of the following elements: 
  1. A number of  assignments submitted during the course.
  2. Final oral exam during the exam period
To achieve a passing grade overall, both elements 1 and 2 must individually meet the learning objectives.
The assessment of element 1 takes place in conjunction with the completion of element 2.
The grade is primarily based on element 2, but element 1 can raise or lower the grade by one grade step.

Indicative number of lessons

72 hours per semester

Teaching Method

Planned lessons: 

Total number of planned lessons: 72 

Hereof: 

Common lessons in classroom/auditorium: 72 

During lectures, concepts, theories and models are introduced and put into perspective. In exercise classes, students train their skills through exercises and dig deeper into the subject matter. 

Other planned teaching activities: 

  • Using the acquired knowledge in projects.
  • Discussing the scientific articles/books/chapters

Teacher responsible

Name E-mail Department
Joan Faye Boyar joan@imada.sdu.dk Algoritmer
Lene Monrad Favrholdt lenem@imada.sdu.dk Algorithms

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study. 
If a transitional arrangement has been made for a course, it will be stated in the list. 
See transitional arrangements for all courses at the Faculty of Science.