Data structures (Hashing, search trees, heaps, union-find, etc.), graph algorithms (shortest path, minimum spanning tree, matching, flow, etc.),
optimization techniques (divide-and-conquer, linear programming, approximation algorithms, etc.), analysis technqiues (amortized analysis, recurrences, average-case analysis etc.).
See the module description for more details.
Prerequisites:
The course requires basic knowledge in algorithms and data structures as covered by the introductory course "Grundzüge von Algorithmen und Datenstrukturen"
Week 07, Dec 01 - Dec 03, MH - Shortest Paths ([MS] Sections 10-10.4, 10.6, 10.7, or [CLRS] Sections 25-25.3, 26.3)
Week 08, Dec 08 - Dec 10, MH - Matroids ([Koz], Lecture 3, Examples), Network Flow ([CLRS] Sections 27-27.2)
Week 09, Dec 15 - Dec 17, MH - Network Flow ([KT] Section 7.4), Mid-Term
Week 10, Jan 05 - Jan 07, MH - Matching ([KT] Sections 7.5, 7.13)
Week 11, Jan 12 - Jan 14, MH - Matching (see here for
a description of the Blossom algorithm), Approximation Algorithms ([KT] Section 11.1, [MS] Section 11.6)
Week 12, Jan 19 - Jan 21, MH - Approximation Algorithms ([KT] Sections 11.3, 11.4, 11.8, 12.4)
Week 13, Jan 26 - Jan 28, MK - Line segment intersections ([CLRS] Section 33.1, 33.2), convex hullls ([CLRS] Section 33.3 and here)
Week 14, Feb 02 - Feb 06, MK - Diametral pair (Sections 1-3 here), Closest pair (Section 1.2 of this book), Range searching (Sections 5.1, 5.3, 5.6 of this book)
Week 15, Feb 09 - Feb 11, MK - String matching ([CLRS] Chapter 32)
Literature/Links:
All 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