AG Algorithmen und Komplexität

Analytic Combinatorics

Robert Sedgewick, Princeton Univ.

Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the scientific analysis of algorithms in computer science and for the study of scientific models in many other disciplines, including probability theory, statistical physics, computational biology and information theory. It is based on using the symbolic method to define generating functions immediately from combinatorial constructions, then directly deriving asymptotic results from those generating functions, using complex asymptotics, singularity analysis, and saddle-point asymptotics.

This course recaps the basics of analytic combinatorics as taught by coursera courses Analytic Combinatorics, Part I & Part II. Participants are recommended to take those courses as preparation of our school.


Analytic Combinatorics for Random Graphs

Michael Drmota, TU Wien

Generating functions and complex asymptotic methods are a proper tool to study several classes of random graphs, for example, random trees, random maps or random planar graphs. The purpose of this course is to give a overview of the methods and results that can be used and obtained in this context. Usually one has to apply a two-step procedure. The first one is to set up relations (functional equations, differential equations, ...) for the generating functions by using combinatorial decomposition schemes. In particular if one is interested in the distribution of a certain graph parameter (number of vertices of given degree, diameter, ...) one needs generating functions with several variables. The second (and usually more challenging one) is to analyze them from an analytic point of view (analyticity, singularities, complex asymptotic methods, ...) in order to characterize the limiting behaviour of the parameters of interest.


Analytic Combinatorics in Bioinformatics

Markus Nebel, Univ. Kaiserslautern, Germany

Random biological sequences are a topic of great interest in genome analysis since, according to a powerful paradigm, they represent the background noise from which the actual biological information must differentiate. Accordingly, we will see how the symbolic method together with techniques from analytic combinatorics can be used to determine the expected number of occurrences of a given motif within a random text. Corresponding results allow to judge the biological importance of the motif under consideration. Afterwards, we switch from one dimensional objects to two dimensional conformations studying RNA secondary structures. We will see how combinatorial as well as stochastic models for those molecules can be mastered using the techniques taught in the previous courses. As a byproduct, algorithms for the random generation of such objects can be derived.

Last but not least we will consider so-called pseudoknots of RNA molecules which are assumed to be part of their tertiary structure. Besides the analytic investigation of those, ways to derive algorithms for structure prediction from our combinatorial or stochastic models will be discussed.


Probabilistic Techniques for the Analysis of Algorithms, with Applications

James Allen Fill, The Johns Hopkins Univ.

Probabilistic techniques provide an indispensable complement to analytic combinatorics in the analysis of algorithms (AofA). This course will be accessible to any graduate student or researcher who has had at least one course in probability and will be most beneficial to those who have had at least one probability course at the measure-theoretic level. A fundamental theme of the course will be that a little knowledge of probability can go a long way in AofA!

The course will review basic topics from the theory of probability that have proved useful in AofA, chosen from such topics as: modes of convergence of sequences of random variables (convergence almost surely, in L^p, in probability, and in distribution), inequalities (such as Holder's inequality, Chebyshev's other inequality, and Chernoff bounds), moment generating functions and characteristic functions, uniform integrability, laws of large numbers, central limit theorems, the method of moments, and martingales. It will provide introductions to more advanced AofA-relevant topics chosen from such topics as: Markov chains, branching processes, urn models, Poissonization (and de-Poissonization), various metrics on distributions, fixed-point characterizations of distributions, convergence of sequences of stochastic processes, perfect simulation using Markov chains (and otherwise), and large deviation principles.

The course will interweave probability theory and applications to AofA, focusing on the fundamentally important and exceptionally rich example of limiting distributions for various ways of measuring the cost of executing the QuickSort and QuickSelect algorithms.