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