Uni-Logo
Algorithms and Complexity
 

Algorithm Theory
Graduate Course - Winter Term 2019/20
Fabian Kuhn

 


Course Description

The design and analysis of algorithms is fundamental to computer science. In this course, we will study efficient algorithms for a variety of basic problems and, more generally, investigate advanced design and analysis techniques. Central topics are algorithms and data structures that go beyond what has been considered in the undergraduate course Informatik II. Basic algorithms and data structures knowledge, comparable to what is done in Informatik II is therefore assumed. The topics of the course include (but are not limited to):

  • Divide and conquer: geometrical divide and conquer, fast fourier transformation
  • Randomization: median, randomized quicksort, probabilistic primality testing
  • Amortized analysis: Fibonacci heaps, union-find data structures
  • Greedy algorithms: minimum spanning trees, scheduling, matroids
  • Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
  • Graph algorithms: network flows, combinatorial optimization problems on graphs

Schedule


The lecture takes place each Thursday, 10:15 to 11:45 am.

There is no lecture on Thursday, 5th December. Instead, we ask you to watch the corresponding video of the 2017/18 lecture (see "Graph Algorithms - Part 2" on the slides and recordings page).

On Tuesday, 4:15 to 5:45 pm, there will be either a lecture or tutorial according to the following schedule:

14.01.20: Tutorial

21.01.20: Lecture

28.01.20: Tutorial

04.02.20: Lecture

11.02.20: Tutorial


Rooms:

Lecture: 101-00-026

German Tutorial (by Pascal Bachor): 101-00-026

English Tutorial (by Johannes Kalmbach): 101-01-016

Exercises

Exercise sheet Due (10.15 am) Solution
Exercise 01 (O-Notation, Divide & Conquer) 31.10.2019 Solution 01
Exercise 02 (FFT, Greedy) 14.11.2019 Solution 02
Exercise 03 (Dynamic Programming, Amortization) 28.11.2019 Solution 03
Exercise 04 (Data Structures) 12.12.2019 Solution 04
Exercise 05 (Maximum Flow and Applications) 09.01.2020 Solution 05
Exercise 06 (Randomization) 23.01.2020 Solution 06
Exercise 07 (Approximation) 06.02.2020 Solution 07
Exercise 08 (Online Algorithms) Solution 08

Submission

You need to submit one solution per group (of at most two people). Submit your exercise solutions via one of the following options:

  • Hand in as hard copy in lecture (before the deadline).
  • Drop a hard copy into the Algorithm Theory [German/English] box in building 051.
  • Send a digital version per mail to your tutor (click on the names below) with the subject 'AT_[SheeetNumber]'

With respect to digital submissions, we prefer solutions prepared with Latex, Word is ok, Scans must be well readable (no photos).

Grading

Your solutions will be graded by one of our tutors, Johannes Kalmbach (English tutorial) or Pascal Bachor (German tutorial). You can pick up your graded solutions during the next tutorial session.

Achieving 50% of the maximum achievable points on the exercise sheets is sufficient to be admitted to the exam.


Lecture Material

All slides and recordings can be found on our Webserver.
Partly, the slides are modifications of earlier versions of Prof. Dr. T. Ottmann and Prof. Dr. S. Albers.


Forum

If you have a question to the lecture or the exercises, please use the forum instead of writing an email. Then all of us and also your colleagues see the question and can answer to it. Feel free to also use the forum to discuss anything related to the topics and organization of the lecture.


Past Exams


Literature

  • Jon Kleinberg and Éva Tardos: Algorithm Design, Addison Wesley
  • Thomas H. Cormen, Charles E. Leiserson, Robert L. Rivest, and Cliford Stein: Introduction to Algorithms, MIT Press
  • Thomas Ottmann and Peter Widmayer: Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag