Vorlesung
"AverageCase Analysis"
Wintersemester 2008/2009
Prof. Dr. Susanne Albers
Dr. Alexander Souza
Lecture
Exam00006 Geb. 79
For remarks and questions please email to Alexander Souza. 
News24.9.2008This page was put online. 27.10.2008 A preliminary version of Chapters 13 is available. Please mail me any error you find. Exercise sheet 1 is available. 28.10.2008 Slides of Chapter 2 are available. 11.11.2008 Exercise sheet 2 is available. 12.11.2008 Slides of Chapter 3 are available. 25.11.2008 Exercise sheet 3 is available. 27.11.2008 Updated versions of Chapters 13 and slides of Chapter 3 are available. 16.12.2008 Chapter 4 is available. 8.1.2009 Chapter 5 and exercise sheet 5 are available. 21.1.2009 Chapter 6 and exercise sheet 6 are available. 10.2.2009 Exercise sheet 7 is available (a little delayed). 11.2.2009 Chapter 7 is available. 16.3.2009 Examdate is out. 

ContentsAn algorithm is intended to solve problems of mathematical kind. As the name suggests, the classical worstcase perspective asks how a given algorithm behaves on the worst possible input. One is usually interested in the running time or approximation ratio of the algorithm. In the averagecase perspective, we are interested in the behaviour of an algorithm "in expectation", i.e., on "typical instances" (whatever this may mean). There are several algorithms that admit bad worstcase behaviour, but which is rarely observed in practice. So, one of the goals of averagecase analysis is to understand why and to close such gaps analytically. As a consequence, additional assumptions on input distributions are necessary. One of the algorithms where a convincing averagecase analysis could be carried out is the wellknown Quicksort. It is not hard to see that it may require n^{2} comparisons for sorting an nelement array. However, only nlog n comparisons are needed with high probability. Highlights:
Basic knowledge in the area of algorithms, optimization, and probability theory are helpful but no prerequisite. 
Lecture Notes and SlidesAvailable when ready. Please mail typos and other errors you find.
Exercise SheetsAssignments to be handed in at the lecture. You will get the corrected assignments back at the exercise sessions.

Further Material
 Probability distributions
 PseudoRandom Number Generation: Knuth: The Art of Computer Programming  Volume 2  Seminumerical Algorithms, Addison Wesley.
 Simulating Random Variables: Ross: Introduction to Probability Models, Harcourt Academic Press.
Books
 M. Mitzenmacher, E. Upfal: Probabilty and Computing, Cambridge University Press.
 R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press.