# Department of Information and Computing Sciences

## Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

# Algorithms and networks

Course code:INFOAN
Credits:7.5 ECTS
Period:period 2 (week 46 through 5, i.e., 13-11-2017 through 2-2-2018; retake week 16)
Timeslot:B
Participants:up till now 41 subscriptions
Schedule:Official schedule representation can be found in Osiris
Teachers:
formgrouptimeweekroomteacher
lecture   Tue 11.00-12.4546-51 BBG-165 Hans Bodlaender
Johan van Rooij

2-4 BBG-165
Thu 15.15-17.0046-51 RUPPERT-D
2-4 RUPPERT-D
Exam:
 week: 5 Thu 1-2-2018 13.30-16.30 uur room: EDUC-MEGARON week: 16 Thu 19-4-2018 13.30-16.30 uur room: BBG-219 retake exam
Contents: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 analyzing 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, kernelization, and some complexity theory.

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).

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

• 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!
Course form:Lectures, two per week. Exercises. Lectures on Tuesdays will be in principal be given by Johan van Rooij and lectures on Thursdays will be in principal be given by Hans Bodlaender.
Exam form:There are a number (7 - 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 above).
• 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.
Minimum effort to qualify for 2nd chance exam:Re-exam: If you have a 4.0 or more for the average, but no sufficient final grade, you can do a re-exam (additional testing). You can also do a re-exam, if you have at least a 5.5 for one of the exams and at least a 6.0 for the average of the exercise sets.

In case of insufficient grade for the exercise: If your average grade is at least 5.2 and the average of your exams is at least 4.8, then you can do instead of a re-exam, an extra written task (aanvullende toets). If you pass this task, then you obtain a 6.0 for the course.

wijzigen?