DM860: Online Algorithms

Study Board of Science

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

STADS ID (UVA): N340035101
ECTS value: 10

Date of Approval: 29-10-2018


Duration: 1 semester

Version: Approved - active

Comment

The Course replace the previous version 15019501 (formerly UVA).

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.

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.

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.

In relation to the competence profile of the degree it is the explicit focus of the course to:
  • Describe, analyze and solve advanced problems in online algorithms using the learned models
  • Analyze the advantages and disadvantages of different quality measures
  • Be able to understand and with a scientific basis reflect on the principles and fundamental properties of online problems and algorithms
  • Give expert knowledge about online algorithms, which is based on the highest level of international research
  • Give knowlede about a variety of specialized models and methods developed in online algorithms, based on the the highest level of international research, including topics from the latest research, such as advice complexity
  • Develop new variants of the methods learned, where concrete problems require it

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 Blackboard for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

June

Tests

Oral exam

EKA

N340035102

Censorship

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

Examination aids

To be announced during the course 

ECTS value

10

Additional information

The Exam consists of:

  • An assignment to be done independently, which will count towards the final grade.
  • Two assignments which can be done in groups, which will count towards the final grade.

In the exam term when the assignments were done, the final grade is given on the basis of an overall assessment of the three assignments and the oral exam. The external examiner will be able to see the assignments. 

The re-exam is an oral exam. External examiner, Danish 7 mark scale. 

Indicative number of lessons

72 hours per semester

Teaching Method

In the intro phase, concepts, theories and models are introduced and put into perspective. In the training phase, students train their skills through exercises and dig deeper into the subject matter. 

Educational activities 

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

Teacher responsible

Name E-mail Department
Joan Boyar joan@imada.sdu.dk

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period