Section outline
-
Description:
This course provides an overview of the different subject areas within algorithms, including a sampling of material on exact, approximation, geometric, and randomized algorithms and on advanced data structures. As such, the course is the basis of the corresponding master-level courses. The course covers improvements on classical algorithms as well as ways to approach NP-hard problems. These approaches range from understanding "good" algorithms to solve the problem exactly to efficient algorithms that solve the problem approximately, and also to randomized approaches which perform well in expectation. Along the way we will see some interesting data structures that can be leveraged.
Learning Objectives:
By the end of this course participants should have a broad overview of advanced topics concerning algorithms (i.e., regarding exact, approximate, geometric, and randomized computations) as well as some advanced data structures. They should be able to analyze and design algorithms of each type and understand the appropriate use of the data structures.
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:
- 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 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 - Computational Geometry: Algorithms and Applications (3rd edition).
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Springer-Verlag, 2008.
Web site with pseudocode for all algorithms - 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.
- Introduction to Algorithms (3rd Edition).
-
Course size:
5 ECTS (2 SWS)
Time & place:
- (most) Lectures on Mondays, 10:15–11:45, room SE III
- (most) Tutorials on Monday, 9:30–10:10, room SE III
NOTE that due to holidays some lectures will occur during the tutorial time slot, and vice versa!
Target group:
Master Computer Science, Master Mathematics, Master Computational Mathematics
Lecturers:
Steven Chaplick, office E12
Alexander Wolff, office E29
Jonathan Klawitter (tutorials), office E33Exam:
Oral exam: (dates to be determined)
Registration in WueStudy required!Pre-requisites:
Algorithmic Graph Theory (recommended)
IMPORTANT NOTES:
1) Lectures will be given in English.
2) Cancellations due to holidays: Friday, 01.11.19 (Allerheiligen).
-
-
Lecture notes of Sabine Storandt's lecture on "Randomized Algorithms" [11.11.19: uploaded newer version] Файл
-
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