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.
D. E. Knuth

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
If you are still a B.Sc. student, you are very welcome to enjoy this lecture already now. Any attainment will be credited for your upcoming Master studies.

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.

Literature

Even More Literature!

Even More Information on Analysis of Algorithms