The first exam is scheduled! Register on RWTHonline!

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 2022/23)

## 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**and

**in person**.

## 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.

## Exercises

Every week we will release an exercise sheet with tutorial and homework exercises. In the tutorial session on Monday, we*together*will solve the tutorial exercises. For the

**exam admission**you have to hand in your solution to the homework exercises one week later in the next tutorial session. Do not be afraid to hand in partial solutions. We want to see you putting thought and effort into the homework. You receive the exam admission if you solve most sheets satisfactory.

- Will be added here during the lecture period.
- Exercise Sheet 01 Solution
- Exercise Sheet 02 Solution
- Exercise Sheet 03 Solution
- Exercise Sheet 04 Solution
- Exercise Sheet 05 Solution
- Exercise Sheet 06 Solution
- Exercise Sheet 07 Solution
- Exercise Sheet 08 Solution
- Exercise Sheet 09 Solution
- Exercise Sheet 10 Solution
- Exercise Sheet 11 Solution
- Exercise Sheet 12 (due date: asap) Solution
- Old Exam 2014 Solution
- Old Exam 2020 Solution

## Books

There is a script that contains all material. It will be provided at the beginning of lectures.- Script
- All chapters

**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.