Topic outline
-
Description:
For many important problems in computer science, no efficient (i.e., polynomial) algorithms are known. A prominent example of this is the Traveling Salesman's Problem (TSP) of finding a shortest round trip that visits a given set of locations. In this lecture, we will discuss the design and analysis of algorithms that may be exponential in the worst case, but are demonstrably faster than obvious brute force approaches. Depending on the interest of the participants, the behavior of such algorithms in practice will also be discussed.
Keywords: Exact exponential algorithms; parameterised algorithms.
Learning Objectives:
By the end of this course, participants should be able to develop and analyze simple exact algorithms. They will also be able to understand and apply basic design techniques, such as branching, dynamic programming, inclusion-exclusion, measure & conquer, kernelization, and search trees with limited depth.
Evaluation:
Grades will be determined by an oral exam at the end of the semester. A bonus of 0,3 points will be awarded to the students who obtain at least 50% of the points on the exercises.
Literature:
- Parameterized Algorithms.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. Springer International Publishing 2015. - https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
- Exact Exponential Algorithms.
Fedor V. Fomin and Dieter Kratsch. Springer-Verlag Berlin Heidelberg 2010.
http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf
- Parameterized Algorithms.
-
Course size:
5 ECTS (2 SWS)
Time & place:
– (most) Lectures on Tuesdays, 12:30–14:00, room SE I
– (most) Tutorials on Fridays, 8:30–10:00, room ÜR I
NOTE: for scheduling reasons some lectures may occur during the tutorial time slot, and vice versa!!!Target group:
Master Computer Science, Master Mathematics, Master Computational Mathematics
Lecturers:
Steven Chaplick (lectures), office E12
Martin Becker (tutorials), Email: martin.b.becker@stud-mail.uni-wuerzburg.de
Alexander Wolff (course coordinator)Exam:
Oral exam (date to be determined)
Registration required!Prerequisite:
Algorithmic Graph Theory (recommended)
NOTE:
Lectures will be given in English.
-
-
-
-
This is the original paper giving the two branching algorithms for satisfiability as discussed in the lecture.
-