2ima00

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||

2ima00 [2016/04/19 14:14] bmpjansen [Contents] |
2ima00 [2016/05/26 12:16] bmpjansen [Student lectures] |
||
---|---|---|---|

Line 21: | Line 21: | ||

==== Prequisites ==== | ==== 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 2IL95. | + | 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. | 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. | ||

Line 27: | Line 27: | ||

==== Organisation ==== | ==== Organisation ==== | ||

- | The course involves literature search, lectures by students based on material provided by the instructors, and weekly homework assignments. Grading will be based on the evaluation of each student's performance in these assignments. There will be no final assignment and no final exam. | + | 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 ==== | ==== Schedule ==== | ||

The kick-off meeting and introductory lecture of the course is on Tuesday 19th April 15:45 - 17:30 in Metaforum 15. | 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. | + | 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. |

- | The detailed schedule for the course will be posted here once the course starts. | + | * 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 | [[http://www.win.tue.nl/~bjansen/courses/2IMA00-1516/Kickoff.pptx|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 ==== | ==== Literature study ==== | ||

Line 74: | Line 107: | ||

=== Topics === | === Topics === | ||

- | An assignment of students to lecture topics will be made during the first week. Possible lecture topics from last year include: | + | The assignment of lectures to students is: |

^ Lecture number ^ Topic ^ Source material ^ Lecturer ^ | ^ Lecture number ^ Topic ^ Source material ^ Lecturer ^ | ||

- | | 1 | More kernelization algorithms | Cygan et al. Chapter 2, **not** 2.5 | ? | | + | | 1 | More kernelization algorithms | Cygan et al. Chapter 2, **not** 2.5 | <del>Boshen</del> Bart | |

- | | 2 | Iterative compression | Cygan et al. Chapter 4, **not** 4.3.2 | ? | | + | | 2 | Iterative compression | Cygan et al. Chapter 4, **not** 4.3.2 | Huib | |

- | | 3 | W[1]-hardness | Cygan et al. Chapter 13 | ? | | + | | 3 | Treewidth | Cygan et al. 7.1-7.3.1 | Henk | |

- | | 4 | Using linear programming in parameterized algorithms | Cygan et al. 2.5 & 3.4 | ?| | + | | 4 | Randomized algorithms | Cygan et al. Chapter 5, **not** 5.4&5.6 | Stefan | |

- | | 5 | Randomized algorithms | Cygan et al. Chapter 5, **not** 5.4&5.6 | ?| | + | | 5 | Advanced kernelization algorithms | Cygan et al. Section 9.1 | Leo | |

- | | 6 | Important separators | Cygan et al. 8.1-8.3 | ? | | + | | 6 | Improving dynamic programming on tree decompositions | Cygan et al. Chapter 11 | Xi | |

- | | 7 | Treewidth | Cygan et al. 7.1-7.3.1 | ? | | + | | 7 | W[1]-hardness | Cygan et al. Chapter 13 | Chris | |

- | | 8 | Advanced kernelization algorithms | Cygan et al. 9.1&9.3 | ? | | + | | 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 === | ||

+ | The literature linked to below can be accessed when logged into the TU/e network, either through VPN or by physically being present at TU/e. | ||

+ | | ||

+ | **Kernels: Chris & Leo.** | ||

+ | | ||

+ | The following paper gives a kernel that is not as small, but is easier to compute, than the one given in the book. In particular, read Section 4 of this paper: | ||

+ | | ||

+ | [[http://dx.doi.org/10.1007/s00224-009-9234-2| | ||

+ | Hans L. Bodlaender, Thomas C. van Dijk: | ||

+ | A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst. 46(3): 566-597 (2010)]] | ||

+ | | ||

+ | Instead of requiring an algorithm to find maximum matchings, it just needs an approximation algorithm for (weighted) feedback vertex set. It was developed independently by 2 sets of authors. Pick the one you find the easiest to read: | ||

+ | | ||

+ | Option 1: | ||

+ | | ||

+ | [[http://dx.doi.org/10.1137/S0895480196305124|Vineet Bafna, Piotr Berman, Toshihiro Fujito: | ||

+ | A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. SIAM J. Discrete Math. 12(3): 289-297 (1999)]] | ||

+ | | ||

+ | Option 2: | ||

+ | | ||

+ | [[https://dx.doi.org/10.1016%2F0004-3702%2895%2900004-6|Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence 83 (1): 167–188]] | ||

+ | | ||

+ | **Treewidth: Henk & Xi.** | ||

+ | | ||

+ | There are 2 approaches for solving the problem when you have a tree decomposition. The first one has a running time of 3^k * poly(n), harder to understand, but may be easier to implement: | ||

+ | | ||

+ | [[https://arxiv.org/pdf/1103.0534v1.pdf|Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time]] | ||

+ | | ||

+ | The next approach has a worse factor f(k), but a better polynomial term (linear), and is conceptually simpler: | ||

+ | | ||

+ | [[http://link.springer.com/chapter/10.1007%2F3-540-36379-3_25|Ton Kloks, C.M. Lee, Jiping Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs]] (page 8 and further) | ||

+ | | ||

+ | I don't know which of the 2 approaches will be faster on the inputs we have; one has a worse polynomial term, the other has a worse factor f(k). I don't think it is feasible to implement both, given the time. Pick one of the two and go for it. | ||

+ | | ||

+ | **Parameterized by solution size (iterative compression & randomized): Huib & Stefan.** | ||

+ | | ||

+ | [[http://dx.doi.org/10.1016/j.ipl.2014.05.001|Tomasz Kociumaka, Marcin Pilipczuk: | ||

+ | Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10): 556-560 (2014)]] |

2ima00.txt · Last modified: 2016/05/26 12:27 by bmpjansen