People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.
Mathematical models have been a crucial inspiration for all scientific activity, even though they are only approximate idealizations of real-world phenomena. Inside a computer, such models are more relevant than ever before, because computer programs create artificial worlds in which mathematical models often apply precisely. I think that's why I got hooked on analysis of algorithms when I was a graduate student, and why the subject has been my main life's work ever since.
Analysis of Algorithms (Winter 2025/26)
Synopsis
This course is about mathematical tools and techniques needed to analyze algorithms rigorously. We will learn how to analyze the average running time of algorithms (as opposed to the worst-case running time), recurrence relations, generating functions, and asymptotic approximations.Language
The entire course (lectures and tutorials) will be in English.Requirements
There are soft requirements for this course: We expect students to have taken basic undergraduate courses in algorithms and programming along with the relevant math courses.Registration
Please register for the lecture so that we can send you emails. There will be no Moodle room. You must, however, register for the final exam.
ECTS Credits
Students will be awarded 8 ECTS credits after passing the final exam.
Lectures, Discussions and Exercise Sessions
There will be two weekly lectures, on Wednesday and Friday. Additionally, there will be a weekly exercise session each Thursday. As Prof. Rossmanith is prevented from giving the lecture in person in the weeks from Oct 22nd to Nov 21st, we will offer a weekly discussion about the lecture instead at the following dates (same time and room as the lecture):
- Wednesday, October 22nd for the 3rd and 4th Video
- Wednesday, October 29th for the 5th and 6th Video
- Friday, November 7th for the 7th and 8th Video
- Wednesday, October 12th for the 9th and 10th Video
- Wednesday, October 19th for the 11th and 12th Video
Video Lectures
The lectures are prerecorded and you can watch the videos yourselves. You can do this whenever you want, but we encourage to watch approximately two lectures each week. Please note that videos differ widely in their lengths with respect to the content, and are not exactly 90 minutes long. The content and presentation is an approximation to the actual in-person lecture.
Exercises
Every week we will release an exercise sheet with exercises. In the tutorial session, we together will solve and discuss (a subset) of the exercises. There will be no mandatory submissions for the admission to the final exam; however, you should feel encouraged to give the exercises a try before the exercise session. A discussion about the homeworks will not be that fruitful if one sees the exercises in the exercise session for the first time.- Exercises will be added here during the lecture period.
- Exercise Sheet 01
- Old Exams for self-assessment at the end of the term:
- Old Exam 2014
- Old Exam 2020
Books
There is a script that contains all material. Moreover, the books that are referred below provide excellent material for this course and should definitely be consulted.- An Introduction to the Analysis of Algorithms
by Robert Sedgewick and Phillippe Flajolet. Read this!
- Analytical Combinatorics (you can download the entire book, for free).
- The Art of Computer Programming (particularly Chapter 1 and all of Volume 3).
- Analysis of Algorithms - Mathematical Methods, Computational Tools.
- Concrete Mathematics.
- Mathematics for the Analysis of Algorithms.
- generatingfunctionology More about generating functions. For the students interested about the formal aspect of generating functions, Chapter 2 is of interest.