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 (Summer 2012)

### Peter Rossmanith

### Synopsis

You will learn the necessary technique that are necessary to analyse the running time of algorithms and apply them on numerous examples. We emphasise both on a very detailed analysis - up to the exact number of machine instructions that are performed on average -, as well as on achiving rough estimates with minimal effort.### Area

**Theoretical Computer Science**

- Master of Science in Computer Science elective course in the area "Theoretical Computer Science"
- Informatik (Diplom), Hauptstudium,

lecture is part of the "Vertiefungsgebiet"*Effiziente Algorithmen* - Informatik (GYM+GS,SII), Hauptstudium
- Software Systems Engineering (M.Sc.),

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

### Language

Lecture will be held in**English**.

### Requirements

The lecture requires content teached in the basic studies/B.Sc. lectures and the corresponding maths lectures.### Registration

No registration is required to attend the lectures or the weekly tutorial.

You must, however, register for the final exam.

### Final Exam

All students who want to participate in the exam must register
in the Campus system here
until 25.05.2012.

To be admitted to the final exam, you will need to have finished at least 50% of homework assignments.

### ECTS Credits

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

### Course Material

There is an L2P-room for this course, where students can discuss questions. Let us know if you have problems entering.

Here are the weekly problem set sheets. Please hand in the homework assignments in the consecutive weeks.

- Problem Set 1, Solutions
- Problem Set 2, Solutions
- Problem Set 3, Solutions
- Problem Set 4, Solutions
- Problem Set 5, Solutions
- Problem Set 6, Solutions
- Problem Set 7, Solutions
- Problem Set 8, Solutions
- Problem Set 9, Solutions
- Problem Set 10, Solutions
- Problem Set 11, Solutions
- Problem Set 12, Solutions

### Literature

- 1st Handout
- Old lecture notes in German
**An Introduction to the Analysis of Algorithms**

by Robert Sedgewick and Phillippe Flajolet.**Read this!**

### Even More Literature!

- Analytical Combinatorics (free download of the entire book possible)
- 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.