DM208: Combinatorial Optimization I (5 ECTS)

STADS: 15007701

Level
PhD course

Teaching period
The course is offered in the autumn semester.
The course is offered according to needs

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal. Kurset kører i 1. kvartal.

Prerequisites:
None

Academic preconditions:
Bachelor degree in computer science or mathematics. Knowledge about the topics of DM508 and DM515

Course introduction
The purpose of the course and its successor Combinatorial Optimization II is to give the student a detailed knowledge of topic within combinatorial optimization. Serveral of the techniques and problems covered in the courses have great pracical relevance. These connections to practical problems will be clarified in the course.

Expected learning outcome
At the end of the course, the student should be able to:
- apply the theory and the algorithms from the course on concrete problem instances
- Give an account of algorithmic and methods covered in the course and give the complexity of the algorithms.
- apply methods, models and algorithmic ideas civered in the course in connection with new problems similar in nature to those covered in the course.

Subject overview
Flows, integer programmeing, matching in graphs, primal-dual algorithms, matroids and the greedy algoritmer, (minimum cost) branchings, Gomory Hu Trees

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Project assignment, Danish 7 mark scale, external examiner)

Re-exam according to the rules of the Study-board.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 22 timer Eksaminatorietimer/opgaveregning: 14 timer
Educational activities

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.

Remarks
Project assignment (take.home exam) handed out in the last week of the course. The student have about 2 weeks to hand in their report.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.