Algorithms and Complexity

Algorithm Theory
Graduate Course - Winter Term 2016/17
Fabian Kuhn


Exam Spring 2017

The exam will take place on Wednesday, September 6, 09:00-11:00 in building 101, room 010/014.

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


Exam date: 28.03.2017, 9:00-11:00
Exam place: Building 101, Room 026

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:


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.



  • Monday 14:15-16:00 : 101-00-026
  • Thursday 10:15-12:00 : 101-00-026


Responsible for the exercises are Mohamad Ahmadi and Philipp Bamberger.

Exercise classes take place (roughly) every second week (usually) on Mondays (tentative).