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

  • Exercise 01 due Oct 31, 2016
  • Exercise 02 due Nov 7, 2016
  • Exercise 03 due Nov 14, 2016
  • Exercise 04 due Nov 21, 2016
  • Exercise 05 due Nov 28, 2016
  • Exercise 06 due Dec 5, 2016
  • Exercise 07 due Dec 12, 2016
  • Exercise 08 due Jan 09, 2017
  • Exercise 09 due Jan 16, 2017
  • Exercise 10 due Jan 23, 2017
  • Exercise 11 due Jan 30, 2017
  • Exercise 12 due Feb 6, 2017
  • Exercise 13 due Feb 13, 2017
  • Schedule

    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