Parameterized algorithms
General data
Course ID: | 1000-2M12APW |
Erasmus code / ISCED: |
11.3
|
Course title: | Parameterized algorithms |
Name in Polish: | Algorytmy parametryzowane |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science |
ECTS credit allocation (and other scores): |
6.00
|
Language: | English |
Type of course: | elective monographs |
Short description: |
The course is devoted to superpolynomial algorithms for NP-hard problems, especially to fixed-parameter algorithms. The target audience are masters and PhD students interested in algorithmics and combinatorics, considering future scientific career (including only at the level of masters thesis). |
Full description: |
The course is devoted to superpolynomial algorithms for NP-hard problems, especially to fixed-parameter algorithms. We plan to present the following topics: 1. Fixed-parameter algorithms: definition, motivation. 2. Branching algorithms. Measure & Conquer analysis. 3. Selected techniques in superpolynomial algorithms: iterative compression, color coding, split&list, divide&conquer, important separators. 4. Applications of the inclusion-exclusion principle, the fast subset convolution algorithm. 5. Algebraic techniques (Schwarz-Zippel and Isolation Lemma). 6. Algorithms in graphs of bounded treewidth. 7. Subexponential algorithms in planar graphs: bidimensionality. 8. Lower bounds: W-hierarchy and Exponential Time Hypothesis. |
Bibliography: |
- Marek Cygan, Fedor Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015. - Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010. - Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, 2006. - Jorg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006. - Rod Downey, Mike Fellows, Parameterized Complexity, Springer, 1999. |
Learning outcomes: |
Knowledge: The student has advanced knowledge on designing and analyzing exact algorithms for NP-hard problems and discovering their limitations (K_W01, K_W02). In particular, the student is able to start (on his own or in a team) research work in the aforementioned directions. Skills: * can design exact algorithm for medium-hard combinatorial NP-hard problem (K_U04) * can (in a rigorous and formal way) analyse an algorithm, proving its correctness and discovering its complexity (K_U04) * understands more specific complexity classes inside the NP class, with the most important case of the W-hierarchy; can place a given problem inside this hierarchy and conduct a simple hardness reduction (K_U05) * can use literature and research articles (in English) (K_U14) * can prepare short notes on a lecture (in English) (K_U13) Competences * understands the need to systematically read scientific articles to broaden and expand knowledge (K_K08) * can formulate precise questions to deepen own understanding of the topic or to find the missing pieces of the reasoning (K_K02) |
Assessment methods and assessment criteria: |
Quizzes after every lecture (via Moodle, 75% solved quizzes results in a +0.5 modifier to the grade from the oral exam), homeworks with problems (total number of points results in a modifier to the grade from the oral exam), and an oral exam (resulting in the final grade). Detailed rules available at moodle. |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-26 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Łukasz Kowalik, Michał Pilipczuk | |
Group instructors: | Łukasz Kowalik, Wojciech Nadara, Michał Pilipczuk | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.