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 2009/2010)
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.
Time and PlaceMonday, 13:30h-15:00h @ room 2356|054 (commonly known as 5054, Computer Science Building).
Friday, 10:30h-12:00h @ room 2356|055 (5055, Computer Science Building).
Start: October, 19th
Weekly TutorialWednesday, 15:45h-17:15h @ seminar room I1, (room 4017)
Start: October, 28th
RequirementsThe lecture requires content teached in the basic studies/B.Sc. lectures and the corresponding maths lectures.
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.
- 1st Handout
- Old lecture notes in German
- An Introduction to the Analysis of Algorithms>
by Robert Sedgewick and Phillippe Flajolet. Read this!
Even Move 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.
Even More Information on Analysis of Algorithms
- Analysis of Algorithms Homepage by Phillipe Flajolet
- Sloane's On-Line Encyclopedia of Integer Sequences
- Micha Hofri's Homepage