Algorithms and Data Structures (Block Course)
WS 2015/2016

News

The re-exam will take place on Wednesday, April 27, at 4pm in Guenter-Hotz-Lecture-Hall.

You must have passed the midterm in order to take this exam. You also must have HISPOS registered for the exam by Tuesday, April 26.

Inspection of the final exam on Tuesday, April 26, at 4pm in E 1 3, Room 415.

Topics

The course will cover basic and advanced data structures and algorithms and their analysis. Examples of data structures are cuckoo hashing, splay trees, randomized search trees, pairing heaps, union-find structures. In terms of algorithms, we first focus on graph problems, such as algorithms for testing connectivity, minimum spanning trees and matroids, shortest path problems, network flows, and matchings. In later parts of the course we will also touch upon more recent topics in algorithms such as approximation algorithms, algorithmic game theory, and lower bound techniques.

Time & Date

This core course will be offered in an intensive block version between February 29 and April 1.

The format of the course will be as follows: A "unit" consists of a 60 minute lecture, followed by 2 hours group work on an exercise sheet, followed by a short discussion section with a tutor. Typically we will have two units a day, the first starting at 9am, the second at 2pm, Monday through Friday, except for Wednesday afternoon, which will be free. A more precise schedule that includes information on the location will be given soon.

This will be a very intensive course. Do not plan on doing anything else seriously beside it.

Assistants

Lavinia Dinu
Email: ldinu at cs.uni-saarland.de
Office hours: Tu, Th 12:00-13:00

Giorgi Nadiradze
Email: gnadiradze at cs.uni-saarland.de
Office hours:

Bojana Kodric
Email: bojana "at" mpi-inf.mpg.de
Office hours:

Paresh Nakhe
Email: pnakhe "at" mpi-inf.mpg.de
Office hours:

---

Grading

Your final grade will be determined by your performance on a midterm exam (40%) and a final exam (60%). There will be a repeat exam for the final. Admittance to the exams requires active participation in the course.

Exams

Midterm: March 17, 2016, 15:00-17:30
Endterm: April 5, 2016, 15:00-18:00
Reexam: April 27, 2016, 16:00-19:00

Literature

K. Mehlhorn, Data Structures and Algorithms, Vols. 1-3, Springer Verlag, 1984
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms - Second Edition, McGraw-Hill, 2001 (ISBN: 0262531968)
J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (ISBN: 0-321-29535-8)
K. Mehlhorn and P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer
D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1991

---

back