Algorithms and Data Structures

Core Course, 4+2

Basic Information

Lectures: Monday + Wednesday, 16:15 - 18:00, E1.3 HS002
Lecturers: Karl Bringmann and Erik Jan van Leeuwen
First lecture: 26 October 2016
Assistant: Andreas Schmid
Tutorials: Thursday 14-16, E1.4 021, Tobias
  Thursday 14-16, E1.4 023, Aruni
  Thursday 16-18, E1.4 021, Philip
  Thursday 16-18, E1.4 023, Bhaskar
  Friday 14-16, E1.4 021, Malte
  Friday 14-16, E1.4 023, Paresh
First tutorial: 3 November 2016
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.


  • On the following dates the tutorial groups in room 021 have to move to room 024: 03, 04, 17, 18, 24, and 25 November
  • You may view your midterm exam papers on Thursday, 5. January 13:30-14:30 in room 305, MPI-Inf

Mailing List

To get news about the lecture, please subscribe to the following mailing list. Note that this is non-binding and does not replace the official registration according to your study program.


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.


Your final grade will be determined by your performance on a midterm exam, final exam, and repeat exam. The final grade is determined as the better of 0.4*midterm + 0.6*final, 0.4*midterm + 0.6*repeat, final, and repeat. Admittance to the exams requires active participation in the course (at least 50% of the points on the first 6 exercise sheets for the midterm, and at least 50% of the total points on all exercise sheets for the final and repeat exam).

Midterm: 14 December 2016, 16:15-18:15, E2.2 Günter-Hotz lecture hall

Final: 1 March 2017, 13:15-16:00, E2.2 Günter-Hotz lecture hall

Repeat: 12 April 2017, 13:15-16:00, E2.2 Günter-Hotz lecture hall

Exercise sheets


Lecture Teacher Topic
26 Oct EJvL Introduction (RAM machine model, big-O notation, data structures). See additional material below and [MS] Sect. 2.1+2.2.
31 Oct KB Randomized Algorithms I (randomized RAM model, quicksort, rank select). See [MS] Sect. 5.4 for quicksort, [GKP] Sect. 1+2 for background on recurrences.
02 Nov KB Randomized Algorithms II (randomized search trees, treaps). See additional material below.
07 Nov EJvL Greedy algorithms (interval scheduling, minimum lateness scheduling). [KT] Sect. 4.1+4.2.
09 Nov EJvL Divide and conquer (recurrences, Akra&Bazzi). [CLRS] Chap. 4 and additional material below.
14 Nov KB Strings I (dynamic programming: longest common subsequence, string matching: Rabin-Karp fingerprinting). [CLRS] Sect. 15.4+32.2.
16 Nov KB Strings II (string matching: Rabin-Karp continued, (Knuth-)Morris-Pratt). [CLRS] Sect. 32.2+32.4.
21 Nov KB Strings III (tries, suffix trees, comparison of string matching solutions). [CR] Sect. 5.
23 Nov EJvL Graphs I (intro, shortest paths I: BFS and Dijkstra). [Sch] Sect 1.1, 1.2 (also [KT] Sect 4.4). See additional material below.
28 Nov EJvL Graphs II (shortest paths II: Bellman-Ford, Floyd-Warshall, Johnson). [Sch] Sect 1.3. [CLRS] Sect. 25.2, 25.3. [MS] Sect 10.7.
30 Nov EJvL Graphs III (matching I: intro, bipartite unweighted). [Sch] 3.2, 3.4.
05 Dec EJvL Graphs IV (matching II: bipartite weighted, general unweighted). [Sch] 3.5, 5.2.
07 Dec EJvL Graphs V (cuts & flow I: intro, max-flow min-cut, Ford-Fulkerson). [Sch] 4.2, 4.3. (See also [KT] 7.1, 7.2 or [CLRS] 26.1, 26.2)
12 Dec EJvL Graphs VI (cuts & flow II: max-flow min-cut, Ford-Fulkerson, Dinits). [Sch] 4.2, 4.3, 4.4 (See also [KT] 7.1, 7.2, 7.3 or [CLRS] 26.1, 26.2)
14 Dec EJvL Midterm (Günter-Hotz lecture hall)
02 Jan KB Canceled
04 Jan KB Polynomials I (polynomial multiplication I: Karatsuba's algorithm, integer arithmetic via reduction to polynomials) [MS] 1.5, [CLRS] 30
09 Jan KB Polynomials II (polynomial multiplication II: Toom-Cook) [MS] 1.5, [CLRS] 30
11 Jan KB Polynomials III (polynomial multiplication III: Fast Fourier Transform, application: sliding window hamming distance) [CLRS] 30
16 Jan EJvL Data Structures I (amortized analysis & union-find). [CLRS] 17.1-3, 21.1. See also additional material below.
18 Jan EJvL Data Structures II (union-find). [CLRS] 21.2, 21.3, 21.4.
23 Jan EJvL Data Structures III (hollow heaps). See additional material below.
25 Jan EJvL Data Structures IV (dictionaries, splay trees, red-black trees).
30 Jan EJvL Data Structures V (cuckoo hashing). See additional material below.
01 Feb KB Geometry I (introduction to computational geometry: representations, primitives, robustness, degeneracies; convex hull algorithms). [BKOS] 1.1-1.2
06 Feb KB Geometry II (orthogonal range searching in 1D and 2D, segment trees). [BKOS] 5.1, 5.3, 10.3
08 Feb KB Geometry III (sweep line algorithms for Klee's measure and line intersection, 2-dimensional linear programming). [BKOS] 2.1, 4.1-4.4
13 Feb KB Geometry IV (more on linear programming, Voronoi diagrams). [BKOS] 7.1-2
15 Feb KB Appetizer (subset sum algorithm). See additional material below.


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

Additional Material