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 2017/18)

The grammar in Sheet 7, H10 was badly defined. This is now fixed.

The Tiling in Sheet 8, H12 was redundant. This is now fixed.

The solution to Sheet 8, H13 is now online.

The Tiling in Sheet 8, H12 was redundant. This is now fixed.

The solution to Sheet 8, H13 is now online.

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

**Theoretical Computer Science**

- Master of Science in Computer Science elective course in the area "Theoretical Computer Science"
- Informatik (GYM+GS,SII), Hauptstudium
- Software Systems Engineering (M.Sc.),

lecture is part of the*Complexity and Algorithm Theory*area of specialization

## 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/programming along with the relevant math courses.## Registration

No registration is required to attend the lectures or the weekly tutorial. You must, however, register for the final exam.

## ECTS Credits

The student will be awarded **8 ECTS** credits
after passing the final exam.

## Course Material

Here are 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.

- Exercise 01, Solution
- Exercise 02, Solution
- Exercise 03, Solution
- Exercise 04, Solution
- Exercise 05, Solution
- Exercise 06, Solution
- Exercise 07, Solution
- Exercise 08, Solution
- Exercise 09, Solution
- Exercise 10
- Chapters 1, 2, 3, and 4 of the script.

## Books

We are (slowly) translating the handouts from German to English. We will upload translations as and when they are ready. However 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.