User Tools

Site Tools


2ima00

This is an old revision of the document!


Seminar Algorithms (2IMA00), 4th Quartile, 2015/2016

Note that the first meeting for this course is on Tuesday 19th April 15:45 - 17:30 (MF15). Please register on OASE before the first meeting.

Instructors

Contents

In this course we study a topic that is on the cutting edge of algorithms research. We will study recent literature on the topic through lectures, given by the students, and by solving problems.

Topics studied in this course vary and usually lie close to the algorithms group's research interests and to (some of) the topics of graduation projects that can be realized within the algorithms group. The focus for this year is on parameterized complexity. This branch of algorithm design aims to deal with NP-complete problems by providing exact algorithms whose running time consists of two parts: a polynomial term in the total size of the input, and a term that is exponential in a complexity parameter k that is assumed to be small in practically relevant inputs. A classic result in the field is that we can test whether an n-vertex graph has a vertex cover of size k in time O(2^k * n). Hence a small solution can provably be found efficiently in a large graph, even though vertex cover is an NP-complete problem. We will study several techniques for designing such fixed-parameter tractable (FPT) algorithms. In addition, we study proof techniques to show that certain problems are unlikely to admit FPT algorithms.

We will use the following literature:

  1. Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. You can download a PDF version of the book from Springer's website when logged into the university network or VPN.

Instead of doing homework exercises to reinforce the theory, we will participate in Track B of the PACE Implementation challenge for parameterized algorithms. Groups of students develop and implement an algorithm to solve the Feedback Vertex Set problem based on the techniques that are covered in the lectures.

Prequisites

You can take this course if you have completed at least one of the courses Advanced Algorithms (2IL45), Geometric Algorithms (2IL55), Algorithms for massive data (2IL75) or Algorithms for geographic data (2IL76) successfully. However, if your study plan allows it, it is better to complete at least two of these courses before taking 2IMA00.

If you have not completed any of the aforementioned courses, but you have completed other Master's courses that are highly relevant to the topic of the seminar, then please contact the instructors to discuss if you can be admitted to the course.

Organisation

The course involves literature search, lectures by students based on material provided by the instructors, and an extensive programming & algorithm engineering assignment. Grading will be based on the quality of the student lectures, on the quality of the developed program, and on the quality of a final report about the implementation project written by each group. There is no final exam.

Grading

Your final grade is computed as (L + P) / 2, rounded up to the nearest integer, where:

  • L is the grade for your student lecture with a resolution of half-points. It is based on your performance during the presentation and on the thoroughness with which you prepared the lecture, as expressed through the quality of your slides and your understanding of the material.
  • P is the grade for the final report of your group's implementation project, with a resolution of half-points. The grade evaluates both the efficiency of the software you developed, as the writing quality of the report.

Schedule

The kick-off meeting and introductory lecture of the course is on Tuesday 19th April 15:45 - 17:30 in Metaforum 15.

After that we will, in principle, meet two times per week. Attendance at all meetings is required. In particular, any student who is absent at the kick-off meeting without prior notice, is assumed not to be taking the course. Afterwards we we will meet two times per week, with some exceptions.

  • Tuesday hours 7+8 (15:45-17:30), MF 15
  • Thursday hours 3+4 (10:45-12:30), MF 13

Please note that the detailed schedule below is tentative and may be adapted during the course.

Week nr. Day Date Time Place Topic Material
1 Tue 19-Apr 15:45-17:30 MF15 Kick-off slides
1 Thu 21-Apr 10:45-12:30 MF13 No meeting
2 Tue 26-Apr 15:45-17:30 MF15 Literature study
2 Thu 28-Apr 10:45-12:30 MF13 Orientation on implementation challenge
3 Tue 03-May 15:45-17:30 MF15 Student lecture 1 (Bart)
3 Thu 05-May 10:45-12:30 MF13 No meeting
4 Tue 10-May 15:45-17:30 MF15 Student lecture 2 (Huib)
4 Thu 12-May 10:45-12:30 MF13 Brainstorm
5 Tue 17-May 15:45-17:30 MF15 Student lecture 3 (Henk)
5 Thu 19-May 10:45-12:30 MF13 Student lecture 4 (Stefan)
6 Tue 24-May 15:45-17:30 MF15 Student lecture 5 (Leo)
6 Thu 26-May 10:45-12:30 MF13 Brainstorm
7 Tue 31-May 15:45-17:30 MF15 No meeting
7 Thu 02-Jun 10:45-12:30 MF13 No meeting
8 Tue 07-Jun 15:45-17:30 MF15 Student lecture 6 (Xi)
8 Thu 09-Jun 10:45-12:30 MF13 Student lecture 7 (Chris)
9 Tue 14-Jun 15:45-17:30 MF15 Student lecture 8
9 Thu 16-Jun 10:45-12:30 MF13 Student lecture 9
9 Thu 16-Jun Afternoon ?? Competition round-up
10 Tue 21-Jun 15:45-17:30 No meeting
10 Thu 23-Jun 10:45-12:30 No meeting
11 Tue 28-Jun 15:45-17:30 No meeting
11 Thu 30-Jun 10:45-12:30 No meeting

Literature study

One of the goals of the seminar is to expose students to research papers and the give insight into the inner workings of the publication process in academia. For this purpose, and to familiarize ourselves with the topic of parameterized algorithms, everyone is assigned a topic for literature study in the first meeting on Tuesday the 19th of April. The possible topics are:

  1. Phylogeny (constructing evolutionary trees that explain how species evolved based on biological data)
  2. Computational geometry (the parameterized analysis of NP-hard problems in computational geometry)
  3. Computational social choice (voting and ranking problems)
  4. Network design (Steiner tree, Maximum Leaf Spanning Tree, etc.)
  5. Route planning (the (Subset) Traveling Salesman problem, the Disjoint Paths problem, etc.)
  6. Clustering (cluster editing, (p,q)-clustering, etc.)
  7. Sequence alignment problems in biology (closest string, common substring, etc.)
  8. Graph modification problems (the study of how much edits are needed to ensure an input graph has a certain property)
  9. Problems in logic (the fixed-parameter tractability analysis of questions related to Satisfiability or similar problems originating in logic such as Constraint Satisfaction)
  10. Implementation and experiments with parameterized algorithms (try keyword: ``algorithm engineering'')
  11. The Feedback vertex set problem
  12. The Vertex Cover problem
  13. The Longest Path (or k-Path) problem
  14. Scheduling problems (graph coloring, scheduling tasks on machines, etc.)

The assignment is as follows. Search for research papers in the field of parameterized algorithms that deal with your topic. (Hint: you can also try keywords fixed-parameter tractability, parameterized complexity, multivariate algorithmics.) This can be done using Google (Scholar), the university library, or other tools that will be discussed in the opening lecture. Make a list of relevant papers and select 3 of them that are interesting to discuss with the rest of the class; for example, pick three papers on the same problem that contain improvements to each other; or pick three that deal with different problems and show the breadth of work on the topic; or pick two with theory and one with experiments. You are free to pick in any way you like, but make a conscious choice that leads to a nice story that you can tell your classmates. Try to read as much of these three papers as you can understand in the time that is available - it may be that this is only the abstract, introduction and conclusion. Then make some notes so that you can talk for roughly 10 minutes about the papers you chose, describing why you chose them, what they are about, and how they relate to each other. This is all done in an informal setting - no Powerpoint slides, but just make some notes on paper so we can have an informed discussion.

Student lectures

General instructions

The general goal of the lectures is to transfer algorithmic ideas to your fellow students. Every lecture has a clearly defined theme. I will indicate on which material from the literature the lecture should be based, and which results have to be covered. Each lecture should be 45 minutes. It is your responsibility to ensure your lecture lasts roughly 45 minutes. 3 minutes more or less is acceptable, but deviating more than that will affect your grade. To this end, it may be useful to have a topic near the end of your lecture that you can skip if you are running out of time (or to cover if you have extra time). For some topics there is some freedom in choosing what to cover, because the literature has too much material for 45 minutes. Use your own best judgement to select material that supports the message of your lecture and transfers the maximum number of interesting algorithmic insights to your fellow students. If there are proofs in the book that are not very relevant to the big picture (for example, that a certain subproblem is polynomial-time solvable, while the crucial point is formed by an insight about an exponential-time procedure), then such proofs can be skipped if needed. However, your lecture should have technical depth and convince your fellow students of the correctness of the approach. The main part of your lecture should be based on PowerPoint / LaTeX beamer slides. However, since proofs are more easy to follow when presented on the whiteboard, your lecture has to contain at least 10 minutes of presenting a proof on the whiteboard.

Do not underestimate the importance of having insightful figures to illustrate the material you are presenting. While figures take a long time to prepare, they are very useful for the audience to understand what is going on.

For more advice, please check out Herman Haverkort's page on how to give a typical talk or lecture in an algorithms seminar.

If you have no idea how to transfer the core algorithmic ideas in a didactically sound way, you could try to use Google to find lectures on related topics for some inspiration. However, since the material is best absorbed by creating all slides yourself, you are not allowed to copy slides from other sources. You are allowed to use up to a handful of images from other sources, if it would be very time-consuming to produce them yourself. In these cases, always give credit to the sources of the imagery.

The grade for your presentation will determine 50% of the grade for this course. We grade two aspects of the presentation: 50% of the grade for the presentation is determined by your preparation and how well you understand the material. The remaining 50% is determined by how well the material is presented.

Topics

The assignment of lectures to students is:

Lecture number Topic Source material Lecturer
1 More kernelization algorithms Cygan et al. Chapter 2, not 2.5 Boshen Bart
2 Iterative compression Cygan et al. Chapter 4, not 4.3.2 Huib
3 Treewidth Cygan et al. 7.1-7.3.1 Henk
4 Randomized algorithms Cygan et al. Chapter 5, not 5.4&5.6 Stefan
5 Advanced kernelization algorithms Cygan et al. Section 9.1 Leo
6 Improving dynamic programming on tree decompositions Cygan et al. Chapter 11 Xi
7 W[1]-hardness Cygan et al. Chapter 13 Chris
8 Using linear programming in parameterized algorithms Cygan et al. 2.5 & 3.4 ?
9 Important separators Cygan et al. 8.1-8.3 ?

Programming pairs for implementation

2ima00.1464255685.txt.gz · Last modified: 2016/05/26 11:41 by bmpjansen