SS26: Advanced Algorithms
Abschnittsübersicht
-
This course provides an overview of various topics in algorithms based on a selection of materials on exact, geometric, randomized, and approximation algorithms, as well as advanced data structures. As such, this course serves as a foundation for the associated master's level courses in algorithms (see: https://www.informatik.uni-wuerzburg.de/algo/lehre/). The course covers improvements to classical algorithms as well as approaches to tackle NP-hard problems. These approaches range from understanding "good" algorithms that solve such problems exactly, to efficient algorithms that approximate such problems, to randomized approaches that work well in expected value. Along the way, we will learn about some interesting data structures that can be exploited for this purpose.
At the end of this course, students should have a rough overview of advanced topics in algorithms and data structures. They should be able to analyze and design algorithms of any type and understand the appropriate use of data structures.
Languages: English (slides, lectures, exercises) – except if all participants understand German Lectures: Tuesdays, 10:15–11:45, ÜR II (M2), starting April 14 Tutorials: Thursdays, 12:30–14:00, ÜR II (M2), starting on April 16 Docents: Alexander Wolff (lectures), Samuel Wolf (tutorials) Oral exams: End of July
Please do not forget to register in WueStudy (Ausgewählte Kapitel der Algorithmik/Theorie/Informatik [Selected Topics in ...]). The deadline is July 15.
The oral exam can be done in English or German (whatever you prefer). It will take approx. 20 minutes per candidate.Credits: 5 ECTS, 2+2 SWS Premises: Algorithms and Data Structures (strongly recommended), Algorithmic Graph Theory (recommended) Target audience: Master Computer Science, Master Mathematics, Master Computational Mathematics Registration:
Please enroll into this WueCampus course room: use the rightmost item in the bar below the course title: "Mich in diesem Kurs einschreiben".
-
Overview of all lectures with slides (for some topics with videos from the course in 2020).
Date (+ long slides) Topic (+ short slides) Videos (old!) Tutorial Literature 14.04.2026 Intro and Organizational Intro -
Every week, we will upload a new exercise sheet at the time of the lecture. Please try to solve the exercises by yourself. In the tutorial, we will discuss the solutions. Due to lack of personnel, the solutions will not be graded, and there will be no bonus, but working on the exercise sheets will help you to pass the oral exam at the end of the teaching period.
-
- Introduction to Algorithms (3rd Edition).
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. MIT Press and McGraw-Hill, 2009 [1990]. - Parameterized Algorithms.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. Springer, 2015.
https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf - Exact Exponential Algorithms.
Fedor V. Fomin and Dieter Kratsch. Springer, 2010.
http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf - Computational Geometry: Algorithms and Applications (3rd edition).
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Springer, 2008.
Web site with pseudocode for all algorithms - Algorithmische Geometrie (2. Auflage). Rolf Klein. Springer, 2005.
- The Design of Approximation Algorithms
David P. Williamson, David B. Shmoys. Cambridge University Press, 2011.
Kostenlose Online-Version
- Approximation Algorithms
Vijay V. Vazirani. Springer, 2003.
-
[Storandt '17] Randomized Algorithms Datei
- Introduction to Algorithms (3rd Edition).