General information

The teachers of Algorithms and Networks are:
  • Johan van Rooij (tuesday). Johan van Rooij works one day per week at Utrecht University: tuesday.
  • Hans Bodlaender (thursday). Hans Bodlaender works four days per week at Utrecht University: tuesday till friday.
The language of the course is English, unless all students following the course are Dutch speaking.

For general information, see the Departments webpage on this course.

Literature

A significant part of the information will be given only in the lectures. Several of the results discussed are very scattered in the literature, and thus it is recommended to follow the attend the lectures, and make your own course notes. If you cannot attend a lecture, it is recommended to borrow and copy course notes from another student.

Recommended books (not obligatory)

None of these books are needed to be able to follow the course. They can be used as additional material and for further 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. Free access from the Utrecht University network
  • Fomin and Kratsch. Exact Exponential Algorithms. Springer, 2010. ISBN 978-3-642-16532-0. Free access
  • 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.

Prerequisites

We expect basic mathematic and algorithmic skills and knowledge. Besides the basics, we also expect the students to be familiar with the theory of NP-completeness. This is taught in courses such as Algorithmiek (bachelor level 3), or Algorithms for decision support (Master, period 1). If you have not taken these courses and want to take the Algorithm and Networks course, please study the chapter on NP-completeness in Cormen et al. (Chapter 34 in the 3th edition of the book).

Similar courses

In the bachelor program Computer Science or Game Technology (in Dutch), the courses Datastructuren and Algoritmiek are a good preparation for this course. Other related bachelor courses are Optimalisering en complexiteit and Discrete wiskunde. Master courses which are recommended when you like the course Algorithms and Networks include: Algorithms for decision support (period 1); Scheduling and Timetabling (period 4); and Geometric Algorithms (period 4).