TU Wien:Fixed-Parameter Algorithms and Complexity VU (Ganian)

Daten

Vortragende	Robert Ganian
ECTS	4,5
Letzte Abhaltung	2023W
Sprache	English
Mattermost	fixed-parameter-algorithms-and-complexity • Register • Mattermost-Infos
Links	tiss:192135, tiss:186855

Zuordnungen

Masterstudium Data Science	Modul BDHPC/EX - Big Data and High Performance Computing - Extension
Masterstudium Logic and Computation	Modul Algorithmics and Complexity (Gebundenes Wahlfach)
Masterstudium Software Engineering & Internet Computing	Modul Algorithmik (Gebundenes Wahlfach)
Masterstudium Technische Informatik	Modul Algorithms and Programming (Gebundenes Wahlfach)

Inhalt

Algorithms, techniques and proofs from the area of fixed-parameter algorithms. Some of the proofs are rather hard, but the lecturer does a good job at explaining them and focuses on the big picture, instead of getting lost in details. Additionally, you do not need to understand the proofs from the lecture to pass the course (although it will probably help when preparing the presentation).

Topics in WS20: The complexity classes FPT, XP and the W-hierarchy. The exponential time hypothesis and techniques to prove lower bounds for kernels (cross composition and polynomial parameter transformations). Techniques to find FPT algorithms or kernels: bounded search trees, color coding, integer linear programing, iterative compression and crown decomposition. Also talked about model checking.

Ablauf

WS17: Blocked on 6 days in January. 4.5 blocks are lectures, the last block is for student presentations.

WS23: Lectures are still blocked in January, whereas the last 1.5 blocks were reserved for presentations. Basically you need to present a paper (conference papers are sufficient) which contains FPT or Kenelization as one of the topics. Afterwards you have to hand-in one of the paper's proofs rephrased in your own words (~1-2 Pages).

Benötigte/Empfehlenswerte Vorkenntnisse

The FPT part from Algorithmics VU is helpful but not required.

Vortrag

In English. Mr Ganian is a great lecturer. He not only presents the results, but usually leads the students to them. The atmosphere is very relaxed.

Übungen

One 20-25 minute presentation of a selected paper from International Symposium on Parameterized and Exact Computation (IPEC). You should present the main results and at least one non-trivial proof from the paper.

WS21: We had the choice to either do a 23-25 minutes paper presentation or to do a 10 minutes presentation and an additional writeup of one proof of the paper.

WS23: This time, there is more freedom in terms of papers which you can choose from. It does not need to be from IPEC, any other CS-Conference is also good (should just not be co-Authore by Robert Ganian, for obvoius reasons...). When you needed to do was a 25-minute paper presentation + (~1-2 Pages) Explanation of one of the Paper's proofs.

Prüfung, Benotung

Doing a fair presentation gets you a "befriedigend (3)", if done rather poorly, the it will yield a "genügend (4)". In order to get a better grade, you need to do an oral exam at the end (volontarily).

WS21: The atmosphere during the exam was very good. He started by asking some basic questions (example of a parameterized problem, definitions of FPT, XP, (polynomial) kernel, parameterized reductions, examples of XP and para-NP-hard problems). For the more advance topics I had the choice between Interative Compression or both ILP and Crown Reductions. I would recommend to prepare one problem for each method / complexity class. The grading was very fair. Little mistakes or "knowledge gaps" were not a big problem and he leads you to a solution if you are stuck somewhere.

WS23: Exam is still held in a good atmosphere. Even if you stumble or mixed-up something, you get chances to correct yourself. There were also no in-depth questions (like explaining the Weft-circuits).

Dauer der Zeugnisausstellung

noch offen

Zeitaufwand

Definitely within 3 ECTS. Attending the 6 lectures takes approx. 6*3=18 hours. Add to that the time required to understand a paper and prepare a presentation (15 hours?), and you have certainly passed the course. To get a better grade than 3, you will have to study for the exam, but if you pay attention during the lectures this shouldn't be too much work.

WS23: It yields 4.5 ECTS rather than 3.

Unterlagen

noch offen

• Materialien

Tipps

• If you enjoyed Robert Ganians part of the Algorithmics VU, then this course is definitely worth doing.

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Diese Seite hat noch keine Anhänge, du kannst aber neue hinzufügen.