Section outline
-
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. 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), German (lectures & exercises for German-speaking audience)
Lectures: Wednesday, 14:15–15:45, ÜR I
Exercises: Monday, 10:15–11:45, ÜR I
Docents: Johannes Zink (Lectures), Alexander Wolff (Lectures), Oksana Firman (Exercises)
Oral Exams: Wednesday, 8. February 2023 and
Wednesday, 5. April 2023.
Please do not forget to register in WueStudy (Ausgewählte Kapitel der Theorie/Algorithmik/Informatik). The deadlines are January 31 and March 31.
Language of the oral exam is English or German.
A grade bonus of 0.3 on the final grade will be given to students who score at least 50% on the exercise sheets.Credits: 5 ECTS, 2+2 SWS Premises: Algorithms and Data Structures (recommended), Algorithmic Graph Theory (recommended) Target audience:
Master Computer Science, Master Mathematics, Master Computational Mathematics
Registration:
If you want to attend this lecture, please enroll here in WueCampus (rightmost item in the bar below the course title: "Mich in diesem Kurs einschreiben"). During the course of the semester, registration in WueStudy will be opened for the exam.
-
Overview of all lectures with slides (for some topics with videos from the previous course in 2020).
-
Every week we will upload a new exercise sheet at the time of the lecture. Deadline for submission is the following lecture session. Achieving at least 50% of the points grants a bonus of one grade level when passing the oral exam.
Exercise sheets may be completed in pairs of two and shall be submitted electronically. We recommend the use of LaTeX and the provided template. You may submit in English (preferred) or German language.
-
- 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 Fitxer
- Introduction to Algorithms (3rd Edition).
Impressum | Datenschutzerklärung - WueCampus | Erklärung zur Barrierefreiheit | Bildnachweise
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon