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)
SynopsisYou 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.
AreaTheoretical 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
LanguageLecture will be held in English.
RequirementsThe lecture requires content teached in the basic studies/B.Sc. lectures and the corresponding maths lectures.
No registration is required to attend the lectures or the weekly tutorial.
You must, however, register for the final exam.
All students who want to participate in the exam must register
in the Campus system here
To be admitted to the final exam, you will need to have finished at least 50% of homework assignments.
The student will be awarded 8 ECTS credits after passing the final exam.
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
- 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.