This special issue is devoted to the Analysis of Algorithms (AofA). Most of the papers are from the Eighth Seminar on Analysis of Algorithms, held in Strobl, Austria, June 23–29, 2002.

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

We give an algorithm that, with high probability, recovers a planted $k$-partition in a random graph, where edges within vertex classes occur with probability $p$ and edges between vertex classes occur with probability $r\ge p+c\sqrt{p\log n/n}$. The algorithm can handle vertex classes of different sizes and, for fixed $k$, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.

We consider Boolean functions over $n$ variables. Any such function can be represented (and computed) by a complete binary tree with and or or in the internal nodes and a literal in the external nodes, and many different trees can represent the same function, so that a fundamental question is related to the so-called complexity of a Boolean function: $L(f):=$ minimal size of a tree computing $f$.

The existence of a limiting probability distribution $P(\cdot)$ on the set of and/or trees was shown by Lefmann and Savický [8]. We give here an alternative proof, which leads to effective computation in simple cases. We also consider the relationship between the probability $P(f)$ and the complexity $L(f)$ of a Boolean function $f$. A detailed analysis of the functions enumerating some sub-families of trees, and of their radius of convergence, allows us to improve on the upper bound of $P(f)$, established by Lefmann and Savický.

The Lehmer–Euclid Algorithm is an improvement of the Euclid Algorithm when applied to large integers. The original Lehmer–Euclid Algorithm replaces divisions on multi-precision integers by divisions on single-precision integers. Here we study a slightly different algorithm that replaces computations on $n$-bit integers by computations on $\mu n$-bit integers. This algorithm depends on the truncation degree $\mu\in ]0, 1[$ and is denoted as the ${\mathcal{LE}}_\mu$ algorithm. The original Lehmer–Euclid Algorithm can be viewed as the limit of the ${\mathcal{LE}}_\mu$ algorithms for $\mu \to 0$. We provide here a precise analysis of the ${\mathcal{LE}}_\mu$ algorithm. For this purpose, we are led to study what we call the Interrupted Euclid Algorithm. This algorithm depends on some parameter $\alpha \in [0, 1]$ and is denoted by ${\mathcal E}_{\alpha}$. When running with an input $(a, b)$, it performs the same steps as the usual Euclid Algorithm, but it stops as soon as the current integer is smaller than $a^\alpha$, so that ${\mathcal E}_{0}$ is the classical Euclid Algorithm. We obtain a very precise analysis of the algorithm ${\mathcal E}_{\alpha}$, and describe the behaviour of main parameters (number of iterations, bit complexity) as a function of parameter $\alpha$. Since the Lehmer–Euclid Algorithm ${\mathcal {LE}}_\mu$ when running on $n$-bit integers can be viewed as a sequence of executions of the Interrupted Euclid Algorithm ${\mathcal E}_{1/2}$ on $\mu n $-bit integers, we then come back to the analysis of the ${\mathcal {LE}}_\mu$ algorithm and obtain our results.

An additive decomposition of a set $I$ of nonnegative integers is an expression of $I$ as the arithmetic sum of two other such sets. If the smaller of these has $p$ elements, we have a $p$-decomposition. If $I$ is obtained by randomly removing $n^{\alpha}$ integers from $\{0,\dots,n-1\}$, decomposability translates into a balls-and-urns problem, which we start to investigate (for large $n$) by first showing that the number of $p$-decompositions exhibits a threshold phenomenon as $\alpha$ crosses a $p$-dependent critical value. We then study in detail the distribution of the number of 2-decompositions. For this last case we show that the threshold is sharp and we establish the threshold function.

This article proposes a surprisingly simple framework for the random generation of combinatorial configurations based on what we call Boltzmann models. The idea is to perform random generation of possibly complex structured objects by placing an appropriate measure spread over the whole of a combinatorial class – an object receives a probability essentially proportional to an exponential of its size. As demonstrated here, the resulting algorithms based on real-arithmetic operations often operate in linear time. They can be implemented easily, be analysed mathematically with great precision, and, when suitably tuned, tend to be very efficient in practice.

We analyse a class of randomized Least Recently Used (LRU) cache replacement algorithms under the independent reference model with generalized Zipf's law request probabilities. The randomization was recently proposed for Web caching as a mechanism that discriminates between different document sizes. In particular, the cache maintains an ordered list of documents in the following way. When a document of size $s$ is requested and found in the cache, then with probability $p_s$ it is moved to the front of the cache; otherwise the cache stays unchanged. Similarly, if the requested document of size $s$ is not found in the cache, the algorithm places it with probability $p_s$ to the front of the cache or leaves the cache unchanged with the complementary probability $(1-p_s)$. The successive randomized decisions are independent and the corresponding success probabilities $p_s$ are completely determined by the size of the currently requested document. In the case of a replacement, the necessary number of documents that are least recently moved to the front of the cache are removed in order to accommodate the newly placed document.

In this framework, we provide explicit asymptotic characterization of the cache fault probability. Using the derived result we prove that the asymptotic performance of this class of algorithms is optimized when the randomization probabilities are chosen to be inversely proportional to document sizes. In addition, for this optimized and easy-to-implement policy, we show that its performance is within a constant factor from the optimal static algorithm.

In this paper, we present several probabilistic transforms related to classical urn models. These transforms render the dependent random variables describing the urn occupancies into independent random variables with appropriate distributions. This simplifies the analysis of a large number of problems for which a function under investigation depends on the urn occupancies. The approach used for constructing the transforms involves generating functions of combinatorial numbers characterizing the urn distributions. We also show, by using Tauberian theorems derived in this paper, that under certain simple conditions the asymptotic expressions of target functions in the transform domain and in the inverse–transform domain are identical. Therefore, asymptotic information about certain statistics can be obtained without evaluating the inverse transform.

Heap ordered trees are planted plane trees, labelled in such a way that the labels always increase from the root to a leaf. We study two parameters, assuming that $p$ of the $n$ nodes are selected at random: the size of the ancestor tree of these nodes and the smallest subtree generated by these nodes. We compute expectation, variance, and also the Gaussian limit distribution, the latter as an application of Hwang's quasi-power theorem.

In this paper, we investigate the limit law of the inertial moment of Dyck paths with respect to the $x$-axis, that is, the sum of the squares of the altitudes. We find its Laplace transform using Louchard's methodology, rediscovering a result which was in fact well known by probabilists. We give recurrence relations which enable us to compute the moments of the joint limit law of the area and the inertial moments of both Dyck paths and Grand Dyck paths (bilateral Dyck paths).

In this paper, we show for generalized $M$-ary search trees that the Steiner distance of $p$ randomly chosen nodes in random search trees is asymptotically normally distributed. The special case $p=2$ shows, in particular, that the distribution of the distance between two randomly chosen nodes is asymptotically Gaussian. In the presented generating functions approach, we consider first the size of the ancestor-tree of $p$ randomly chosen nodes. From the obtained Gaussian limiting distribution for this parameter, we deduce the result for the Steiner distance. Since the size of the ancestor-tree is essentially the same as the number of passes in the (generalized) Multiple Quickselect algorithm, the limiting distribution result also holds for this parameter.

Let $F(\b{z})=\sum_\b{r} a_\b{r}\b{z^r}$ be a multivariate generating function that is meromorphic in some neighbourhood of the origin of $\mathbb{C}^d$, and let $\sing$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $\sing$.

In the first article in this series, we treated the case of smooth points of $\sing$. In this article we deal with multiple points of $\sing$. Our results show that the central limit (Ornstein–Zernike) behaviour typical of the smooth case does not hold in the multiple point case. For example, when $\sing$ has a multiple point singularity at $(1, \ldots, 1)$, rather than $a_\b{r}$ decaying as $|\b{r}|^{-1/2}$ as $|\b{r}| \to \infty$, $a_\b{r}$ is very nearly polynomial in a cone of directions.

We show that, for a certain class of probabilistic models, the number of internal nodes $S_n$ of a trie built from $n$ independent and identically distributed keys is concentrated around its mean, in the sense that $\Var S_n=\Oh(\EE S_n)$. Keys are sequences of symbols which may be taken from varying alphabets, and the choice of the alphabet from which the $k$th symbol is taken, as well as its distribution, may depend on all the preceding symbols. In the construction of the trie we also allow for bucket sizes greater than 1. The property that characterizes our models is the following: there is a constant $C$ such that for any word $v$ that may occur as a prefix of a key the size $S^v_n$ of a trie built from the suffixes of $n$ independent keys conditioned to have the common prefix $v$ has the property $\EE S^v_n\leq Cn$. This class of models contains memoryless and Markovian source models as well as the probabilistic dynamical source models that were recently introduced and thoroughly developed by Vallée [Algorithmica29 (2001) 262–306], in particular the continued fraction source. Furthermore we study the external path length $L_n$, which obeys $\EE L_n=\Oh(n\ln n)$ and $\Var L_n=\Oh(n\ln^2 n)$.