|Website:||website containing additional information|
|Period:||period 3 (week 6 through 15, i.e., 3-2-2020 through 9-4-2020; retake week 27)|
|Participants:||up till now 43 subscriptions|
|Schedule:||Official schedule representation can be found in Osiris|
|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 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.
|Literature:||Most literature will be handed out during the course or can be downloaded from the website.
|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:
|Minimum effort to qualify for 2nd chance exam:||Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn.|