DM860: Online Algorithms
- Be able to use basic probability, and analyze algorithms.
- 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
- 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
- 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
Exam element a)
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
- Using the acquired knowledge in projects.
- Discussing the scientific articles/books/chapters