Algorithms and Complexity

Algorithm Theory
Graduate Course - Winter Term 2012/13
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 beyon what has been considered in the undergraduate course Informatik II. Basic algorithms and data structures knowledge, comparable to what is done in Informatik II, or , 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, etc.
  • Amortized analysis: binomial queues, Fibonacci heaps, union-find data structures
  • Greedy algorithms: minimum spanning trees, bin packing problem, scheduling
  • Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
  • Graph algorithms: network flows, combinatorial optimization problems on graphs


The exam questions will be in English, however it will be ok to answer the questions in German. Everyone is allowed to bring 5 handwritten A4 pages, a pocket calculator, and a dictionary to the exam. No other material is allowed!

To get a feeling for the type of questions, here are the last two exams: Note however that the set of topics of the 2011/12 lecture on which the second exam was based was not the same as this time.

Course Evaluation

Please fill out the online course evaluation form.



  • Tuesday 08:30-10:00 (no break): 101-00-026
  • Wednesday 16:15-18:00: 101-00-026, every second week
    Wednesday lecture dates: 24.10., 31.10., 14.11., 28.11., 12.12., 9.1., 23.1., 6.2.


The exercises are supervised by Hamid Ghods. Exercise classes take place every two weeks in the weeks where there is no lecture.

Day Time Room Teaching Assistant Language
Wednesday 16-18 051-00-006 Evis Plaku English
Wednesday 16-18 101-00-026 Fabian Reiter German
Thursday 16-18 051-00-006 Hamid Ghods English

(Here is a list of the tutorial groups (Update November 20). The password is the last name of the lecturer)

Lecture Material

Slides / Recordings

  • 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.


Problem Set Assigned Due Solution / Additional Material

Problem Set 1 24.10.2012 31.10.2012

Problem Set 2 31.10.2012 14.11.2012

Problem Set 3 14.11.2012 28.11.2012

Problem Set 4 28.11.2012 12.12.2012

Problem Set 5 12.12.2012 9.1.2013

Problem Set 6 9.1.2013 23.1.2013

Problem Set 7 24.1.2013 6.2.2013


  • 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
  • Jon Kleinberg and Éva Tardos: Algorithm Design, Addison Wesley
  • lecture of last year: Alex Souza: Graduate Course "Algorithm Theory", Winter Term 2011/12