# Algorithms and Data Structures

## 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

## 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

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