| Algorithms and Data Structures 2 [2024 SoSe] | ||
|---|---|---|
| Code IADS2 |
Name Algorithms and Data Structures 2 |
|
| CP 8 |
Duration one semester |
Offered every winter semester |
| Format Lecture 4 SWS + Exercise course 2 SWS |
Workload 240h; thereof 90h lectures and tutorials, 15h exam preparations, 135h lecture wrap-up and homework |
Availability B.Sc. Angewandte Informatik B.Sc. Informatik M.Sc. Angewandte Informatik M.Sc. Scientific Computing |
| Language English |
Lecturer(s) Christian Schulz |
Examination scheme |
| Learning objectives | Students: - understand fundamental theoretical and practical concepts of advanced algorithms and data structures, - get to know established methods and algorithms, - are familiar with issues of efficient implementations, - are able to identify/formulate algorithmic problems in/for different application areas, - are able to analyse new algorithms as well as analysing their running time, and select appropriate algorithms for applications - are able to apply algorithms and data structures to real-world problems, and can objectively assess the quality of the results |
|
| Learning content | Introduction to Algorithm Engineering: - advanced data structures (efficient addressable priority queues, monotone priority queues, external priority queues), - advances graph algorithms (strongly connected components, shortest paths, maximum flows / min s-t cuts, min-cost flows), techniques to solve problems to optimality (branch-and-bound, branch-and-reduce, dynamic programming, integer linear programming as a modelling tool), - introduction to randomized algorithms, greedy algorithms, approximation algorithms, advanced string algorithms, geometric algorithms, external memory algorithms |
|
| Requirements for participation | recommended are: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Mathematik für Informatiker 1 (IMI1) oder Lineare Algebra 1 (MA4) | |
| Requirements for the assignment of credits and final grade | The module is completed with a graded oral examination. The final grade of the module is determined by the grade of the examination. The requirements for the assignment of credits follows the regulations in section modalities for examinations. | |
| Useful literature | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009, ISBN 978-0-262-03384-8, pp. I-XIX, 1-1292 Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures: The Basic Toolbox. Springer 2008, ISBN 978-3-540-77977-3 Jon M. Kleinberg, Éva Tardos: Algorithm design. Addison-Wesley 2006, ISBN 978-0-321-37291-8, pp. I-XXIII, 1-838 Stefan Näher: LEDA, a Platform for Combinatorial and Geometric Computing. Handbook of Data Structures and Applications 2004 |
|