SluitenHelpPrint
Switch to English
Cursus: INFOAN
INFOAN
Algorithms and networks
Cursus informatie
CursuscodeINFOAN
Studiepunten (EC)7,5
Cursusdoelen
After completing this course, the student will have: 
- knowledge of important network algorithms
- knowledge of important algorithmic techniques and concept
and 
- the ability to model problems from applications as an (algorithmic) network problem
- the ability to apply algorithmic techniques, to solve algorithmic network problem
- the ability to prove correctness of a network algorithm
- the ability to formulate graph and network algorithms
- the ability to analyze the running time of network algorithms

Assessment
There are a number (7 to 8) exercise sets, and two exams.
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.

The exercise sets count for 30 percent of the end note, and the two exams each for 35 percent.

A repair test requires at least a 4 for the original test.

Prerequisites
Students are expected to have a level of understanding of mathematics and algorithms as taught in the bachelor course Algoritmiek (bachelor level 3).

Similar skills can be acquired, for example through the Algorithms for decision support course (Master, period 1), or a number of courses from a bachelor in Mathematics.

Additionally, students are expected to be familiar with the theory of NP-completeness.
This is taught in the above mentioned courses (Algoritmiek or Algorithms for decision support). If you are unfamiliar with this topic, please read the chapter in the book by Cormen et al. on NP-Completeness (Chapter 34 in the 3th edition of the book).

When in doubt about whether you satisfy these prerequisites, please contact the course coordinator.


 

Inhoud
Systems and programs are designed for many purposes and in many ways, but it's algorithms that make things work. Good algorithm design requires understanding and modelling an application, and subsequently studying and analysing the computational features of the design. In this course, we study a number of advanced techniques for efficient algorithm design, often at the hand of problems from networks and graphs.

In many applications, networks and graphs are used as a model. Typical examples are networks of roads, or electronic networks. In other applications, the graph model may be less obvious, but appears to be very useful, like for scheduling problems. In this course, we look to the translation of problem to network model, and we look to algorithmic problems and their solutions on networks and graphs.

Some topics are: shortest paths, flow, matchings, stable marriage and stable roommates problems, planar graphs, triangulated graphs, treewidth, graph isomorphism, exact exponential-time algorithms, approximation algorithms, fixed parameter tractability, kernelisation, and some complexity theory.

Course form
Lectures, exercises

Literature
Most literature will be handed out during the course or can be downloaded from the website.

Recommended reading:

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, Third Edition. MIT Press / McGraw-Hill, 2001. ISBN 978-0-262-03384-8.
  • Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh. Parameterized Algorithms. Springer, 2015. ISBN 978-3-319-21274-6.
  • Fomin and Kratsch. Exact Exponential Algorithms. Springer, 2010. ISBN 978-3-642-16532-0.
  • Ausiello, Crescenzi, Gambosi, Kann, Marchetti Spaccamela, Protasi. Complexity and Approximation. Springer, 1998. ISBN 978-3-540-65431-5.
  • Kleinberg and Tardos. Algorithm Design. Pearson / Addision Wesley, 2005. ISBN 978-0-321-29535-4.
  • Ahuja, Magnanti, Orlin. Network Flows. Pearson, 1993. ISBN-13: 978-0-136-17549-0.
  • Schrijver. Combinatorial Optimization. Polyhedra and Efficiency. Springer, 2003. ISBN 978-3-540-44389-6.

Note that these books are not obligatory. Participation in classes is recommended: much is not covered in the books !

SluitenHelpPrint
Switch to English