Perfilado de sección
-
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), German (lectures & exercises for German-speaking audience) Lectures: Wednesday, 14:15–15:45, ÜR I (Informatikgebäude) Exercises: Monday, 16:00–17:30, HS 4 (Naturwissenschaftlicher Hörsaalbau), first exercise on Monday, 23.10.2023 Docents: Johannes Zink (Lectures), Oksana Firman (Exercises) Oral exams: Tuesday, 27.02.2024 and Wednesday, 17.04.2024
Please do not forget to register in WueStudy (Ausgewählte Kapitel der Algorithmik/Theorie/Informatik [Selected Topics in ...]). The deadlines are January 31 and March 31, respectively.
Language of the oral exam is English or German. It will take approx. 20 minutes per candidate.
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:
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).
-
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. To produce figures, ipe (https://ipe.otfried.org/) can be a helpful tool. You may submit in English 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 Archivo
- 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