DM860: Online Algorithms (10 ECTS)

STADS: 15019501

Level
Master's level course approved as PhD course

Teaching period
The course is offered in the spring 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.

Prerequisites:
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

Subject overview
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

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:

1. Oral exam. Danish 7 mark scale, external examiner.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 36 hours
Skills training phase: 36 hours, hereof:
 - Tutorials: 36 hours

Educational activities

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

Educational form


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.