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.
D. E. Knuth

Analysis of Algorithms (Winter 2020/21)

Please visit the moodle room for information about the exam!

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

No registration is required to attend the lectures or the weekly tutorial. If you register, you will have access to the moodle room with the latest materials and zoom links. You must, however, register for the final exam.

ECTS Credits

Students will be awarded 8 ECTS credits after passing the final exam.

Course Material

The lectures are prerecorded and you should watch the videos yourselves. You can do this during the official time slots, which are from 8:30-10.00 am on Mondays and Tuesdays or whenever you want. Due to the Corona crisis no lecture halls can be used. Please note that videos differ widely in their lengths and are not exactly 90 minutes long. Please watch the first two videos until Tuesday evening (October 27). The first four chapters and part of the fifth chapter of the script are available for reading. The videos are available in the Moodle room to which you gain access by registering for the lecture in RWTH Online.

The tutorial on Wednesdays is held from 2:30-4:00 pm via video conference. The corresponding Zoom link will be provided at the start of the first week.

Here we provide the weekly problem sets. You are encouraged to do the homework and discuss and work in groups. However, they will not be scored and are not mandatory for the exam.

Exercises

Books

There is a script that contains all material. It will be provided at the beginning of lectures. Moreover, the books that are referred below provide excellent material for this course and should definitely be consulted.

More Information on Analysis of Algorithms