DM817: Network Programming: Theory and Applications

Study Board of Science

Teaching language: Danish, but English if international students are enrolled
EKA: N340083102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master's level course approved as PhD course

STADS ID (UVA): N340083101
ECTS value: 10

Date of Approval: 05-02-2022


Duration: 1 semester

Version: Approved - active

Comment

The course is offered as needed and is not necessarily offered every year. Examination for DM817 are offered according to the following plan when the course is offered: Ordinary examination (January), first re-examination (March) and 2nd re-examination in (June).

Examination for DM817 (part of courses offered E22) are offered: Ordinary examination January 2023, first re-examination March 2023 and 2nd re-examination in June 2023.

Entry requirements

None

Academic preconditions

Students taking the course are expected to:
  • Have knowledge basic algorithms such as those taught in DM507.
  • Have knowledge of basic mathematical argumentation including mathematical induction and proof by contradiction.
  • Have knowledge about complexity of algorithms.
  • Have knowledge of basic datastructures such as those taught in DM507

Course introduction

The aim of the course is to enable the student to:
  • Apply flow methods as an important tool for solving practical optimization problems. Besides standard flow problems, examples are matching problems, orientation problems and simple scheduling problems.
  • Model various optimization problems as flow problems.
  • Apply the theory of flows to show that a given problem can be efficiently solved.
  • Use flow theory to derive structural descriptions of optimal solutions for certain optimization problems.
  • Explain the algorithms from the course and apply these to problems resembling those from the course.
  • Formulate a (generalized) flow model from a problem description in words.
  • Explain algorithms from the course in which flow algorithms form a subcomponent, e.g. increasing the edge-connectivity of digraphs, matchings in bipartite graphs and scheduling algorithms.
The course builds on the knowledge acquired in the courses DM507 Algorithms and data structures and DM553 Complexity and Computability. 

The course gives a foundation for elective courses within combinatorial optimization and grafteoretical topics. The course also gives a solid foundation for writing a master thesis with the area of graph algorithms and all flow related areas.
In relation to the competence profile of the degree it is the explicit focus of the course to enable the student to:
  • Analyze and solve advanced problems by use of flow methods.
  • Develop new variants of the learned flow methods in order to apply these to new problems.
  • Solve practical optimization problems by use of flow methods.

Expected learning outcome

The learning objectives of the course is that the student demonstrates the ability to:
  • Apply the theory of network flows as a tool for solving problems which resemble those from the course
  • Apply flow algorithms as subroutines in more complex algorithms
  • Evaluate whether one can model a given problem, resembling those from the course, as a flow problem.
  • Argue about the complexity of algorithms which are based on flow algorithms.
  • Explain generalizations of flows and explain by examples how these expand the range of applications of the theory.
  • Apply the theory and algorithms from the course to solve practical optimization problems such as flow problems, transportation problems, matching problems, simple scheduling problems and orientation problems for (road) networks.

Content

The following main topics are contained in the course:
  • Shortest paths
  • Flows and minimum cost flows
  • Polynomial algorithms for flow problems
  • Scheduling including project planning
  • Flows with convex cost functions
  • Submodular flows
  • Graph connectivity
  • Matchings in graphs
  • Primal dual algorithms

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

January 

Tests

Oral exam

EKA

N340083102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

Duration

30 minutes preparation and 30 minuttes examination

Examination aids

To be announced during the course.

ECTS value

10

Indicative number of lessons

45 hours per semester

Teaching Method

The teaching method is based on three phase model.
  • A large part of the intro phase will consist of video lectures which the participants will watch and then discuss the content of these with the teacher at weekly physical meetings. Selected topics will be covered at the physical meetings.
  • The skills training phase will consist of solving problems posed on the weekly notes. Solutions to these problems will be covered partly via videos and partly at the weekly physical meetings.
Activities during the study phase:
  • Solution of weekly assignments in order to discuss these at the weekly meetings.
  • Self study of various parts of the course material.
  • Reflection upon the intro and training sections.
    The intro phase consists of (video) lectures by the teacher. Here we cover theory and methods and these are illustrated through examples. The intro phase is complemented by the skills training phase in which the students each week are working with new assigments covering the topics currently studied. Finally, the study phase consists of further independent reading of and reflection upon the course materials.

Teacher responsible

Name E-mail Department
Jørgen Bang-Jensen jbj@imada.sdu.dk Algoritmer

Timetable

Administrative Unit

Institut for Matematik og Datalogi (matematik)

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.