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

# 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

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

# 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