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
Assessment: 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: Archive
Comment
The Course replace the previous version 15019501 (formerly UVA).
The course is offered as needed and is not necessarily offered every year. 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 needed and is not necessarily offered every year. 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.
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
Examination regulations
Exam element a)
Timing
June
Tests
Oral exam
EKA
N340035102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Duration
30 minutes
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
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
- Using the acquired knowledge in projects.
- Discussing the scientific articles/books/chapters