Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Teaching

Algorithms and Data Structures (Winterterm 14/15)

Lecturers:
Dr. Martin Hoefer
Dr. Michael Kerber

Contents:
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"
The language of the lecture is English.

Organization:
Lectures: Monday 10:15-12:00, Wednesday 14:15-16:00, HS 001, Building E1 3
Start of teaching: October 22
End of teaching: February 11
Seasonal break: December 22 - January 4

Exercise groups:
The exercises take place in the MPI building (E 1.4), ground floor.
  • Monday 14-16, Heads: Daniel Vaz, Room 021
  • Monday 14-16, Tails: Aruni Choudhary, Room 023
  • Monday 16-18, Heads: Wanchote Jiamjitrak, Room 021
  • Monday 16-18, Tails: Omar Darwish, Room 023
  • Tuesday 14-16, Heads: Bojana Kodric, Room 021
  • Tuesday 14-16, Tails: Andreas Schmid, Room 023
Exams:
Mid-term: December 17, 14:00 - 16:00, HS I, Building E2 5 (Mathematics), results are here.
Final: February 20, 09:00-12:00, Günther-Hotz-Hörsaal, Building E2 2, results are here
Re-exam: April 13, 09:00-12:00, Günther-Hotz-Hörsaal, Building E2 2, results are here

Communication:
Mailing list: Follow the instruction of the web interface. After successful subscription, post your messages to algodat_ws1415@lists.mpi-inf.mpg.de
Office hours:
  • Michael Kerber: By arrangement
  • Martin Hoefer: By arrangement
Registration:
Please register for the course in the Hispos system (if needed).

Exercise Sheets:
Solutions are due on Wednesdays, at the beginning of the lecture.
  1. [Sheet 00] (due Oct 29)
  2. [Sheet 01] (due Nov 05)
  3. [Sheet 02] (due Nov 12)
  4. [Sheet 03] (due Nov 19)
  5. [Sheet 04] (due Nov 26)
  6. [Sheet 05] (due Dec 03)
  7. [Sheet 06] (due Dec 10)
  8. [Sheet 07] (due Dec 19)
  9. [Sheet 07(b)] (due Jan 07)
  10. [Sheet 08] (due Jan 14)
  11. [Sheet 09] (due Jan 21)
  12. [Sheet 10] (due Jan 28)
  13. [Sheet 11] (due Feb 04)
  14. [Sheet 12] (due Feb 11)

Exam/Credit Points:
The lecture is worth 9 LP, if
  • 50% of the exercises points are obtained
  • both mid-term and final exam are passed or the re-exam is passed
  • The final grade is determined by the exams (the better of {(40% mid-term + 60% final),grade of re-exam})
Schedule (tentative):
  • Week 01, Oct 22 - Oct 22, MH - Logistics, Stable Matchings ([KT] Section 1.1)
  • Week 02, Oct 27 - Oct 29, MK - Mathematical Preliminaries ([MS] Sections 2.1 to 2.3.3, A.3), basic data structures ([MS] Section 3 except 3.3))
  • Week 03, Nov 03 - Nov 05, MK - Quicksort ([MS] Section 5.4) Hashing ([CLRS] Section 11, alternatively: [MS] Section 4), Bloom filter (see also this book), Cuckoo hashing
  • Week 04, Nov 10 - Nov 12, MK - (2,4)-trees ([MS] Section 7.2 or [Meh] III 5.2), Splay trees ([Koz], Lecture 12), binary heaps ([MS] Section 6.1)
  • Week 05, Nov 17 - Nov 19, MK - Fibonacci heaps ([MS] Section 6.2), Union-find ([Koz], Lecture 10+11)
  • Week 06, Nov 24 - Nov 26, MH - Connected Components ([MS] Sections 9.2-9.4)
  • 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

More Courses of the Algorithms and Complexity Group