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 transform
  • 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 Th. Ottmann und P. Widmayer is a prerequisite for understanding the topics of this course (see also Lecture "Informatik II").


  • lecture 3 hours per term and exercise 1 hour per term, both in English ("3V+1Ü SWS")
  • ECTS: 6