2022 Autumn 2020 Autumn 2018 Spring 2016 Spring 2013 Autumn 2012 Spring 2011 Spring 2009 Spring
Show the courses of study containg this course Se overgangsordninger
Dansk English

DM817: Network Programming: Theory and Applications (10 ECTS)

STADS: 15005701

Level
Master's level course approved as PhD course

Teaching period
The course is offered when needed.
To be announced.

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
Group Type Day Time Classroom Weeks Comment
Common I Monday 14-16 IMADA semi 15
Common I Monday 12-16 IMADA semi 17
Common I Monday 12-14 IMADA semi 18
Common I Tuesday 14-16 IMADA semi 12
Common I Wednesday 12-14 IMADA semi 12
Common I Wednesday 14-16 IMADA semi 15-16
Common I Thursday 10-12 U7 5,8-11
Common I Thursday 10-12 IMADA semi 6-7,16
Common I Friday 11-13 IMADA semi 5-11
H1 TE Monday 09-11 U155 6
H1 TE Monday 10-12 IMADA semi 7-8
H1 TE Monday 14-16 IMADA semi 16
H1 TE Wednesday 12-14 IMADA semi 9-11
H1 TE Thursday 12-14 IMADA semi 5,15
H1 TE Thursday 10-12 U153 12
H1 TE Thursday 10-12 IMADA semi 18
H1 TE Friday 10-12 IMADA semi 16
Show entire timetable
 Show personal time table for this course.

Comment:
Ubegrænset deltagerantal

Prerequisites:
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.
 


Subject overview
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
    Meddeles ved kursets start


Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
  1. Project assignments. (10 ECTS). External marking, 7-mark scale. 
A closer description of the exam rules will be posted under 'Course Information' on Blackboard.
Reexam is an oral presentation.
 


Expected working hours
The teaching method is based on three phase model.
Intro phase: 40 hours
Skills training phase: 26 hours, hereof:
 - Tutorials: 26 hours

Educational activities
  • Solution of weekly assignments in order to discuss these in the exercise sections.
  • Solving the project assigments
  • Self study of various parts of the course material.
  • Reflection upon the intro and training sections.
  •  
Educational form
The intro phase consists of 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 as well as solution of the two sets of problems which constitute the exam.

Language
This course is taught in English, if international students participate. Otherwise the course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.