Algorithms and Complexity

Algorithm Theory
Graduate Course - Winter Term 2015/16
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, 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


Post-Exam Review: Friday, September 23, 2016, 14:00-15:00 in room 106-00-004.

The exam questions will be in English. Everyone is allowed to bring 5 handwritten A4 pages (corresponds to 5 single-sided A4 sheets!), 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 exams:

Note however that the set of topics of the 2011/12 lecture on which the fall 2012 exam was based was not the same as this time.



  • Monday 14:15-15:00 : 101-00-026
  • Thursday 10:15-11:45 : 101-00-026


Responsible for the exercises are Mohamad Ahmadi and Oleksii Saukh.

Exercise tutorials will (usually) be weekly on Mondays from 15:15-16:00. Any changes to the this schedule will be announced here.