After completing this course, the student will have
- knowledge of important network algorithms
- knowledge of important algorithmic techniques and concepts
- ability to model problems from applications as an (algorithmic) network problem
- ability to apply algorithmic techniques, to solve algorithmic network problems
- ability to prove correctness of a network algorithm
- ability to formulate graph and network algorithms
- ability to analyze the running time of network algorithms
Assessment
There are a number (approximately 6) exercise sets, and two exams.
The exercise sets count for 30 percent of the end note, and the two exams each for 35 percent.
The exercises sets will be peer-reviewed in class during a session in which the teachers will explain the solutions of the exercises.
In order to pass the course, you need:
- an average grade of at least 5.5 (computation of the average is explained at the course website).
- at least an average grade of 6.0 on the exercises.
- an average of at least 5.0 for the exams.
A repair test requires at least a 4 for the original test.
Prerequisites
We expect basic mathematic and algorithmic skills and knowledge.
Besides the basics, we also expect the students to be familiar with basic algorithmic paradigms and the theory of NP-completeness.
This is taught in courses such as INFOAL Algorithmiek (bachelor level 3), or INFOMADS Algorithms for decision support (master).
If you have not taken these courses (or any other equivalent course) it may be hard to keep up with the pace of the course.
Contact the course coordinator if you’re in doubt
|
 |
|
In this course a number of advanced techniques for efficient algorithm design are studied, often at the hand of problems from networks and graphs.
Networks and graphs are often used as a basic model, both to model practical application, and as a theoretical object to study and design algorithms for.
Typical examples of networks are networks of roads, electronic networks, social networks.
In other applications, the graph model may be less obvious, but appears to be very useful, like for scheduling problems.
In this course, the translation of problem to network model is treated, and algorithmic problems and their solutions on networks and graphs are looked into.
This is done in two parts: the first part is on important fundamental graph algorithms with both practical and theoretical implications, namely maximum flow/minimum cut, minimum cost flows, (stable) matchings, Euler tours, planar graphs).
The second part focuses on getting familiar with a broader range of fields of algorithmic study involving graphs (fixed parameter tractability, exact exponential-time algorithms, probabilistic/randomized algorithms, tree width, approximation algorithms and complexity theory).
Course form
Lectures.
Literature
Most literature will be handed out during the course
|
|
|