Intendierte Lernergebnisse
After successful completion of this course, students will know methods and corresponding theorems in (analytic) combinatorics as listed in the contents section below. They will understand and will be able to prove these theorems and will be able to apply these methods to the analysis of algorithms.
Lehrmethodik
Lecture with an emphasis on examples concerning the analysis of algorithms.
Inhalt/e
"Analysis of Algorithms" is something of a misnomer - "Analytic Combinatorics" or "Asymptotic Methods" are perhaps better and less scary titles. This course discusses tools which are useful in determining the asymptotic behaviour of functions. As an example, the factorial function n! can be approximated by sqrt(2 pi n)*(n/e)^n. These tools are very useful in combinatorial analysis, for example in determining an approximation for large coefficients of a given generating function which are in turn used to analyse algorithms.Contents:Introduction. Example: Sorting algorithms.Generating Functions (Review and Advanced Techniques)Mellin Transform and Mellin-Perron SummationSingularity AnalysisSaddle-Point MethodLimiting Distributions (Overview)
Erwartete Vorkenntnisse
Basic knowledge on generating functions is useful, a review will be given at the beginning of the course. Complex analysis is an important tool.
Curriculare Anmeldevoraussetzungen
It will be beneficial to have completed courses in Complex Analysis and Combinatorics.
Literatur
R. Sedgewick and Ph. Flajolet, An Introduction to the Analysis of Algorithms (Book Site, Lecture Videos)Ph. Flajolet and R. Sedgewick, Analytic Combinatorics (Book Site, PDF Version, Lecture Videos)Ph. Flajolet, X. Gourdon, Ph. Dumas, Mellin Transforms and Aysmptotics: Harmonic Sums