Bachelor
Informatica
Informatiekunde
Kunstmatige intelligentie
Master
Computing Science
Game&Media Technology
Artifical Intelligence
Human Computer Interaction
Business Informatics

Website: | website containing additional information | ||||||||||||||

Course code: | INFOAN | ||||||||||||||

Credits: | 7.5 ECTS | ||||||||||||||

Period: | period 3 (week 6 through 15, i.e., 8-2-2021 through 16-4-2021; retake week 27)
| ||||||||||||||

Timeslot: | B | ||||||||||||||

Participants: | up till now 40 subscriptions | ||||||||||||||

Schedule: | Official schedule representation can be found in MyTimetable | ||||||||||||||

Teachers: |
| ||||||||||||||

Contents: | Systems and programs are designed for many purposes and in many ways, but it's algorithms that make things work. 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: network flows, matchings, stable marriage and stable roommates problems, planar graphs, treewidth, graph isomorphism, exact exponential-time algorithms, approximation algorithms, fixed parameter tractability, kernelisation, randomised algorithms, and some complexity theory.
| ||||||||||||||

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.
not obligatory, but they can be used to find more information or a different exposition of the topics covered by the lectures. Participation in the lectures is highly recommended. | ||||||||||||||

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 Jesper Nederlof. | ||||||||||||||

Exam form: | There are a number of exercise sets (6-8) 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.
| ||||||||||||||

Minimum effort to qualify for 2nd chance exam: | To qualify for a 2nd chance exam, you need a final grade of at least 4. |