Algorithms and Complexity

Graduate Course
"Algorithms Theory"
Winter Term 2011/12
Alexander Souza

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 c.t.: 101-00-026
  • Wednesday 16-17 c.t.: 101-00-026

Course Evaluation

Slides / Recordings

  • All slides and recordings can be found on our webserver.
    The slides are modifications of earlier versions of Prof. Dr. Ottmann and Prof. Dr. Albers.

Exercise courses

The exercise courses are supervised by Thomas Janson.

They take place every two weeks.

Day Time Room Teaching Assistant Language
Thursday 8-10 101-01-018 Ahmed Mahdi english
Thursday 8-10 051-00-034 Florian Geißer german
Friday 12-14 101-00-018 Julian Jarecki german

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


Exercise sheets

Sheet Publication Submission Discussion
Assignment 1 October 26 November 2 November 10/11
Assignment 2 November 9 November 16 November 24/25
Assignment 3 November 23 November 30 December 8/9
Assignment 4 December 7 December 14 December 22/23
Assignment 5 December 21 January 11 January 19/20
Assignment 6 January 18 January 25 February 2/3
Assignment 7 February 1 February 8 February 16/17

Final exam

  • Credit points: 6
  • Date final exam: 27.02.2012 at 9:00-10:30 in room 101-00-026 and 101-00-036.
  • Eligibility: at least 50% of the points in the exercises, one black board presentation.
  • Registration: Via the web-page of the "Vorlesungsverzeichnis" until 11.2.2012.
  • Announcement in the Lecture of 21.12.2011: video, pdf, pdf 4up, pdf with annotations
  • Permitted resources: one on both sides handwritten DIN A4 page and a non-programmable calculator.