Algorithms and Data Structures

Core Course, 4+2

Basic Information

Lectures: Tuesday + Friday, 10:15 - 12:00, virtually
Lecturers: Karl Bringmann and Marvin Künnemann
First lecture: 3 November 2020
Assistant: Alejandro Cassis
Tutorials: tba
First tutorial: tba
Credits: 9
Prerequisites: The course requires basic knowledge in algorithms and data structures as covered by the introductory course "Grundzüge von Algorithmen und Datenstrukturen".
Language: The language of the course is English.

News

Contents

Data Structures (hashing, union-find, etc.), graph algorithms (shortest path, matching, flow, etc.), optimization techniques (divide-and-conquer, approximation algorithms, etc.), analysis techniques (amortized analysis, recurrences, average-case analysis, etc.), computational geometry (convex hull, segment tree, etc.), strings and polynomials. See the module description for more details.

Schedule

Lecture Teacher Topic
3 Nov  
6 Nov  
10 Nov  
13 Nov  
17 Nov  
20 Nov  
24 Nov  
27 Nov  
1 Dec  
4 Dec  
8 Dec  
11 Dec  
15 Dec  
18 Dec  
5 Jan  
8 Jan  
12 Jan  
15 Jan  
19 Jan  
22 Jan  
26 Jan  
29 Jan  
2 Feb  
5 Feb  

Literature

Most books are provided in the library's "Semesterapparat". The course will not follow a particular book.

  • [MS] K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox, Springer, 2008 (ISBN: 9783540779773)
  • [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms - Second Edition, McGraw-Hill, 2001 (ISBN: 0262531968)
  • [KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (ISBN: 0-321-29535-8)
  • [Meh] K. Mehlhorn, Data Structures and Algorithms, Vols. 1-3, Springer Verlag, 1984
  • [Koz] D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1991
  • [GKP] R. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994
  • [CR] M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994
  • [Sch] A. Schrijver, A Course in Combinatorial Optimization, 2013 (see pdf link in additional material)
  • [BKOS] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer Verlag, 2000