
DM892: Approximation and online algorithms
The Study Board for Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340129102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master
STADS ID (UVA): N340129101
ECTS value: 10
Date of Approval: 15-03-2023
Duration: 1 semester
Version: Approved - active
Comment
Entry requirements
Academic preconditions
Academic preconditions. Students taking the course are expected to be able to:
- design and analyze algorithms
The material from DM507/DM578/DS814 is required to be known.
It is an advantage to know the contents of DM553 Complexity and Computability and to have a basic knowledge of linear programming.
Course introduction
Many tasks such as planning and scheduling can be formulated as discrete optimization problems, but most often they cannot be solved optimally within a reasonable amount of time. Here, approximation algorithms play an important role.
An approximation algorithm is an optimization algorithm with a guaranteed running time and solution quality. For example, we will learn a simple and fast algorithm for finding a TSP-tour that is at most 50% longer than an optimal tour.
The course builds on the knowledge acquired in the course DM507/DM578/DS804 Algorithms and Data Structures. References to concepts from DM553 Complexity and Computability as well as DM545/DM871 Linear and Integer Programming can also occur during the course.
The course provides a basis for a master thesis with approximation and/or online algorithms.
In relation to the competence profile of the degree it is the explicit focus of the course to:
- Describe, analyse, and solve advanced computer scientific problems using the models learned in the course.
- Give the skills to analyze the advantages and disadvantages of various algorithms, especially in terms of resource consumptions
- Give the skills to develop new variants of the methods learned where the specific problem requires
- Be able to understand and with a scientific basis reflect on the principles and fundamental properties of approximation and online algorithms.
- Give expert knowledge about approximation and online algorithms.
- Give knowledge about a variety of specialized models and methods developed in approximation and online algorithms, based on the the highest level of international research, including topics from the latest research
Expected learning outcome
The learning objective of the course is that the student demonstrates the ability to:
- Give concise descriptions of the problems considered in the course
- Describe the algorithms learned in the course, concrete algorithms as well as algorithm paradigms
- Analyze known and new algorithms, particularly with respect to the approximation factor but also with respect to running time and space consumption
- Assess which methods are appropriate to use in the context
- Adapt known algorithms to special cases of known problems and to new problems
- Design and analyze new algorithms for problems similar to problems considered in the course
Content
The following main topics are contained in the course:
- Approximation factor and competitive ratio
- Running time and space consumption
- Combinatorial algorithms, LP-based algorithms, greedy algorithms
- Deterministic and randomized algorithms
- Concrete optimization problems such as TSP, scheduling, knapsack, bin packing, and caching
Literature
Examination regulations
Exam element a)
Timing
January
Tests
Oral examination
EKA
N340129102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card - Name
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
10
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
- Intro phase: 36 hours
- Training phase: 36 hours
Activities during the study phase:
- Solution of weekly assignments in order to discuss these in the exercise sections.
- Self study of various parts of the course material.
- Reflection upon the intro and training sections.
Teacher responsible
Timetable
Administrative Unit
Team at Registration
Offered in
Recommended course of study
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.