Algorithms and Complexity

Graduate Course
"Algorithms Theory"
Winter Term 2010/11
Matthias Westermann

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 very basic problems and, more generally, investigate advanced design and analysis techniques. Central topics are some algorithms and data structures which have not at all or not sufficiently extensive been discussed in the undergraduate course Informatik II. These include, but are not limited to:

  • Divide and conquer: geometrical divide and conquer, fast Fourier transformation
  • Randomization: randomized quicksort, probabilistic primality testing, RSA, univeral and perfect hashing
  • Amortized analysis: binomial queues, Fibonacci heaps, union-find data structures
  • Greedy procedures: shortest path, minimum spanning trees, bin packing problem, scheduling
  • Graph algorithms
  • Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
  • String matching and text compression: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, suffix trees, Huffman coding, Lempel-Ziv-Welch data compression algorithm

The knowledge of algorithms and data structures described in chapters 1 to 6 of the book "Algorithmen und Datenstrukturen" by Thomas Ottmann and Peter Widmayer is a prerequisite for understanding the topics of this course.


  • Tuesday 16-18: HS 00-026, 101
  • Wednesday 16-18: HS 00-026, 101

Exercise courses

The exercise courses are supervised by Marco Muñiz.

They take place every two weeks and start on 08.11.2010.

Day Time Room Teaching Assistant Language
Tuesday 12-14 051-00-034 Ahmed Mahdi English
Wednesday 12-14 051-00-031 Julian Jarecki German
Thursday 12-14 101-00-010/014 Ahmed Mahdi English
Thursday 12-14 101-01-009/013 Florian Geißer German
Thursday 14-16 051-00-031 Florian Geißer German
Friday 12-14 051-00-006 Julian Jarecki German

Exercise sheets

The solutions can be submitted in English or German and in groups up to two students. Please write down your name, your matriculation number, and the name of your tutor at the head of each sheet. Drop it into the box in building 051 ground floor which is labeled with the name of your tutor. You can hand in your solution by mail, too. Please ask your tutor for his mail address.

Final exam

  • Credit points: 6
  • Date final exam: 09.03.2011 at 10:15-11:45 in room 101-00-026 and 101-00-036.
  • Date exam inspection: 10.03.2011 at 12:30-14:00 in room 051-02-026.
  • Eligibility: at least 50% of the points in the exercises.
  • Permitted resources: one on both sides handwritten DIN A4 page and a non-programmable calculator.



  • 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