Registration for this course is open until Tuesday, 26.03.2024 23:59.


Currently, no news are available

Algorithms and Data Structures (block course)

The course will cover basic and advanced data structures and algorithms, as well as their analysis. Examples of data structures are perfect hashing, splay trees, randomized search trees, union-find structures. In terms of problem domains, we cover graphs, strings, polynomials, and geometry. Furthermore, we discuss algorithm analysis techniques such as amortization and randomization, and general algorithm design principles.

Time, Date, and Format

This core course will be offered in an intensive block version between February 28 and March 26. The course can be taken only in presence.

The format of the course will be as follows: A "unit" consists of a 70 minute lecture, followed by 2 hours of group work on an exercise sheet, followed by a short discussion section with a tutor (tutorial). Typically we will have two units a day, the first starting at 9am, the second at 2pm, Monday through Friday, except for Wednesdays, which will have only the morning unit. As an exception, the first lecture happens on February 28 at 14:00. See Information→Timetable for details.

The lecture will take place in room HS003 in building E1 3.

The tutorial will take place at 12:00 and at 17:00 in seminar room SR016 in building E1 3. The rooms 016 in building E1 3 and 106 in building E1 1 are reserved throughout the whole lecture period as working space.

This will be a very intensive course. Do not plan on doing anything else serious beside it.


You need to register on this webpage to get access to exercise sheets and other course material.


You grade will be determined by a written exam. Admittance to the exams requires active participation in the course.

Endterm: tba

Re-Exam: tba


The course requires basic knowledge in algorithms and data structures as covered for example by the course “Introduction to Algorithms and Data Structures” (“Grundzüge von Algorithmen und Datenstrukturen”). In particular, you should be familiar with correctness proofs of algorithms. Specific concepts that you should have basic familiarity with and should be able to apply include:

  • pseudocode notation
  • O-notation, running time analysis
  • binary search
  • basic sorting algorithms (e.g. mergesort)
  • arrays, linked lists
  • stacks, queues
  • heaps / priority queues
  • binary search trees, balanced binary search trees (e.g. AVL trees)
  • definition of a graph
  • graph traversal (e.g. depth first search / breadth first search)

In case you want to read up on these topics we recommend the videos of the course “Introduction to Algorithms and Data Structures”, see Information→Materials.

Tentative List of Topics

  • greedy algorithms
  • dynamic programming
  • divide and conquer (e.g. master theorem, integer multiplication, FFT)
  • randomized algorithms (e.g. quicksort, randomized search trees, hashing)
  • amortization (e.g. Fibonacci heaps, union find)
  • strings (e.g. pattern matching, tries)
  • graphs (e.g. shortest paths, maxflow, matching)
  • computational geometry
Date Lecturer Topic Comment
28.2. 2pm   Intro: machine model, O-notation  
29.2. 9am   Greedy and Dynamic Programming I  
29.2. 2pm   Dynamic Programming II  
1.3. 9am   Divide and Conquer I: basic examples, master theorem  
1.3. 2pm   Divide and Conquer II: Strassen, Karatsuba  
4.3. 9am   Divide and Conquer III: Toom-Cook, FFT  
4.3. 2pm   Divide and Conquer IV: applications of FFT  
5.3. 9am   Randomized I: model, quicksort, rank select  
5.3. 2pm   Randomized II: dictionaries, randomized search trees, treaps  
6.3. 9am   Randomized III: hashing  
7.3. 9am   Randomized IV: more on hashing  
7.3. 2pm   Randomized V: algorithms that work with high probability  
8.3. 9am   Amortization I: intro  
8.3. 2pm   Amortization II: Fibonacci heaps / hollow heaps  
11.3. 9am   Amortization III: splay trees  
11.3. 2pm   Amortization IV: union find  
12.3. 9am   Strings I: longest common subsequence  
12.3. 2pm   Strings II: string matching: Rabin-Karp, Knuth-Morris-Pratt  
13.3. 9am   Strings III: string matching continued, tries  
14.3. 9am   Strings IV: suffix trees  
14.3. 2pm   Graphs I: intro, BFS+DFS, Dijkstra  
15.3. 9am   Graphs II: shortest path: Bellman-Ford, Floyd-Warshall, Johnson, ...  
15.3. 2pm   Graphs III: more shortest paths  
18.3. 9am   Graphs IV: minimum spanning tree  
18.3. 2pm   Graphs V: maxflow: intro, maxflow mincut  
19.3. 9am   Graphs VI: maxflow: Ford-Fulkerson  
19.3. 2pm   Graphs VII: maxflow: blocking flows  
20.3. 9am   Graphs VIII: maximum matching  
21.3. 9am   Graphs IX: global mincut  
21.3. 2pm   Geometry I: intro, convex hull  
22.3. 9am   Geometry II: convex hull ctd., orthogonal range searching  
22.3. 2pm   Geometry III: orthogonal range searching ctd.  
25.3. 9am   Geometry IV: sweep line  
25.3. 2pm   Geometry V: Voronoi diagrams  
26.3. 9am   Teaser: SAT Algorithms  
26.3. 2pm   Teaser: Fine-Grained Complexity  


The course will not follow a particular book. The following is a list of literature that could be useful.

  • [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
  • [BKOS] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer Verlag, 2000
  • [Eri] J. Erickson, Algorithms, 2019 (Free electronic version)
Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.