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 2014)
Peter Rossmanith
Final Exam
The final exam will be held on the 11th of August, Monday at 10:00 am in room 5056. The exam will be an open-book exam and is 2 hours long. You are allowed to bring a copy of the course textbook (Analysis of Algorithms by Sedgewick and Flajolet) and a copy of the course notes by Peter Rossmanith. If you bring in additional material, please let us know.
The final exam questions with solutions: Final Exam
Final Exam Scores
| Matriculation Number | Point Grade |
|---|---|
| 297694 | 1.0 |
| 307861 | 1.0 |
| 258853 | 2.7 |
| 304097 | 1.0 |
| 287394 | 2.3 |
| 307855 | 1.0 |
| 334537 | 2.0 |
| 337622 | 2.7 |
| 342902 | 2.0 |
| 341488 | 1.7 |
Synopsis
This course is about mathematical tools and techniques needed to analyse algorithms rigorously. We will learn how to analyse 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 (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
The entire course (lectures and tutorials) will be in English.Requirements
There are some 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 discuss and work in groups. However note that you must write down your own solutions (preferably in Latex) and hand in (or email) the solutions within a week of getting the assignment.
- 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
Handouts/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.- Old lecture notes in German
- Latest Set of Notes (parts of which are in German)
- An Introduction to the Analysis of Algorithms
by Robert Sedgewick and Phillippe Flajolet. Read this!
More Books!
- 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.