Analysis of algorithms is concerned with accurate estimates of complexity parameters of algorithms and aims at predicting the behaviour of a given algorithm run in a given environment. It develops general methods for obtaining closed-form formulae, asymptotic estimates, and probability distributions for combinatorial or probabilistic quantities, that are of interest in the optimization of algorithms. Interest is also placed on the methods themselves, whether combinatorial, probabilistic, or analytic. Combinatorial and statistical properties of discrete structures (strings, trees, tries, dags, graphs, and so on) as well as mathematical objects (e.g., continued fractions, polynomials, operators) that are relevant to the design of efficient algorithms are investigated.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour as classical […]

By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for […]

Consider $ m $ copies of an irreducible, aperiodic Markov chain $ Y $ taking values in a finite state space. The asymptotics as $ m $ tends to infinity, of the first time from which on the trajectories of the $ m $ copies differ, have been studied by Szpankowski (1991) in the setting of tries. We […]

The objective of this paper is to find in a setting of n sequential observations of objects a good online policy to select the k bestof these n uniquely rankable objects. This focus is motivated by the fact that it is hard to find closed form solutions of optimalstrategies for general k and n. […]

The partial sum of the states of a Markov chain or more generally a Markov source is asymptotically normally distributed under suitable conditions. One of these conditions is that the variance is unbounded. A simple combinatorial characterization of Markov sources which satisfy this condition is […]

The new finite state machine package in the mathematics software system SageMath is presented and illustrated by many examples. Several combinatorial problems, in particular digit problems, are introduced, modeled by automata and transducers and solved using SageMath. In particular, we compute the […]

In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of […]

The successive discrete structures generated by a sequential algorithm from random input constitute a Markov chain that may exhibit long term dependence on its first few input values. Using examples from random graph theory and search algorithms we show how such persistence of randomness can be […]

We introduce and study a combinatorial optimization problem motivated by the question in the title. In the simple case where you use all objects in your room equally often, we investigate asymptotics of the optimal time to clean up in terms of the number of objects in your room. In particular, we […]

Flood-it is a combinatorial game played on a colored graph G whose aim is to make the graph monochromatic using the minimum number of flooding moves, relatively to a fixed pivot. Free-Flood-it is a variant where the pivot can be freely chosen for each move of the game. The standard versions of […]

Let fm,n,h be the number of spanning forests with h edges in the complete bipartite graph Km,n. Kirchhoff\textquoterights Matrix Tree Theorem implies fm,n,m+n-1=mn-1 nm-1 when m ≥1 and n ≥1, since fm,n,m+n-1 is the number of spanning trees in Km,n. In this paper, we give an algorithm […]

The classic Coupon-Collector Problem (CCP) is generalized. Only basic probability theory is used. Centerpiece rather is an algorithm that efficiently counts all k-element transversals of a set system.

Let T be a d-dimensional toroidal grid of n^d points. For a given range parameter ω, and a positive integer k ≤q d, we say that two points in T are mutually visible if they differ in at most k coordinates and are a distance at most ω apart, where distance is measured using the \ellₚ norm. We obtain […]

In the running time analysis of the algorithm Find and versions of it appear as limiting distributions solutions of stochastic fixed points equation of the form X D = Sigma(i) AiXi o Bi + C on the space D of cadlag functions. The distribution of the D-valued process X is invariant by some random […]

We study a leader election protocol that we call the Swedish leader election protocol. This name comes from a protocol presented by L. Bondesson, T. Nilsson, and G. Wikstrand (2007). The goal is to select one among n > 0 players, by proceeding through a number of rounds. If there is only one player […]

What today we call digital search tree (DST) is Coffman and Eve's sequence tree introduced in 1970. A digital search tree is a binary tree whose ordering of nodes is based on the values of bits in the binary representation of a node's key. In fact, a digital search tree is a digital tree in which […]

We adapt a novel idea of Cichon's related to Approximate Counting to the present instance of Digital Search Trees, by using m (instead of one) such trees. We investigate the level polynomials, which have as coefficients the expected numbers of data on a given level, and the insertion costs. The […]

Cuckoo hashing is a hash table data structure offering constant access time, even in the worst case. As a drawback, the construction fails with small, but practically significant probability. However, Kirsch et al. (2008) showed that a constant-sized additional memory, the so called stash, is […]

A partition of $x > 0$ of the form $x = \sum_i 2^{a_i}3^{b_i}$ with distinct parts is called a double-base expansion of $x$. Such a representation can be obtained using a greedy approach, assuming one can efficiently compute the largest \mbox{$\{2,3\}$-integer}, i.e., a number of the form $2^a3^b$, […]

In the extensible bin packing problem we are asked to pack a set of items into a given number of bins, each with an original size. However, the original bin sizes can be extended if necessary. The goal is to minimize the total size of the bins. We consider the problem with unequal (original) bin […]

For Dyck paths (nonnegative symmetric) random walks, the location of the first maximum within the first sojourn is studied. Generating functions and explicit resp. asymptotic expressions for the average are derived. Related parameters are also discussed.

We start with a set of $n$ players. With some probability $P(n,k)$, we kill $n-k$ players; the other ones stay alive, and we repeat with them. What is the distribution of the number $X_n$ of \emph{phases} (or rounds) before getting only one player? We present a probabilistic analysis of this […]

Priority trees are a certain data structure used for priority queue administration. Under the model that all permutations of the numbers 1, . . . , n are equally likely to construct a priority tree of size n we study the following parameters in size-n trees: depth of a random node, number of right […]

In this paper we consider the distribution of a pattern of interest in a binary random (d; k)-sequence generated by a Markov source. Such constrained sequences are frequently encountered in communication systems. Unlike the previous approach based on generating function we have chosen here to use […]

A binary sequence of zeros and ones is called a (d; k)-sequence if it does not contain runs of zeros of length either lessthan d or greater than k, where d and k are arbitrary, but fixed, non-negative integers and d < k. Such sequences find requires that (d; k)-sequences do not contain a specific […]

In words, generated by independent geometrically distributed random variables, we study the lth descent, which is, roughly speaking, the lth occurrence of a neighbouring pair ab with a>b. The value a is called the initial height, and b the end height. We study these two random variables (and some […]

We consider questions concerning the tileability of orthogonal polygons with colored dominoes. A colored domino is a rotatable 2 × 1 rectangle that is partitioned into two unit squares, which are called faces, each of which is assigned a color. In a colored domino tiling of an orthogonal polygon P, […]

The β-numeration, born with the works of Rényi and Parry, provides a generalization of the notions of integers, decimal numbers and rational numbers by expanding real numbers in base β, where β>1 is not an integer. One of the main differences with the case of numeration in integral base is that the […]

We analyse the asymptotic behaviour in the mean of a non-commutative rational series, which originates from differential cryptanalysis, using tools from probability theory, and from analytic number theory. We derive a Fourier representation of a first-order summation function obtained by […]

In a recent paper Broutin and Devroye (2005) have studied the height of a class of edge-weighted random trees.This is a class of trees growing in continuous time which includes many wellknown trees as examples. In this paper we derive a limit theorem for the internal path length for this class of […]

Exponential bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees or in recursive algorithms. In particular they arise as parameters of divide and conquer type algorithms. We derive tail bounds […]

In a barter exchange market, agents bring items and seek to exchange their items with one another. Agents may agree to a k-way exchange involving a cycle of k agents. A barter exchange market can be represented by a digraph where the vertices represent items and the edges out of a vertex indicate […]