DM892: Approximation and online algorithms

Study Board of 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

The course is offered when needed.

Entry requirements

The course cannot be chosen by students who have passed DM865 or DM833.

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

See itslearning for syllabus lists and additional literature references.

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

Language

Normally, the same as teaching language

Examination aids

To be announced during the course

ECTS value

10

Indicative number of lessons

72 hours per semester

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

Name E-mail Department
Lene Monrad Favrholdt lenem@imada.sdu.dk Algoritmer

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

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.