Algorithms & Complexity
English

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.

News

  • 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.

https://lists.mpi-inf.mpg.de/listinfo/algodat-ws16

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.

Exams

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

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.

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

Additional Material

Lecture 1: Data Structures and Simple Operations

Lecture 3: Randomized Search Trees

Lecture 5: Proof of the Akra & Bazzi theorem as presented in class, by Kurt Mehlhorn. See also the notes on the Akra & Bazzi theorem by Tom Leighton.

Lecture 9-14: A Course in Combinatorial Optimization (free pdf)

Lecture 9: Six degrees of separation, Kevin Bacon number, Erdös number, How Facebook computes its separation number

Lecture 20: Experiments on Union-Find Algorithms (also references many variants)

Lecture 22: Hollow heaps

Lecture 24: Cuckoo hashing: "Cuckoo Hashing" by Pagh & Rodler, and "An Overview of Cuckoo Hashing" by Charles Chen

Lecture 29: Subset Sum Algorithm