Analysis of Algorithms

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.


Sequential selection of the k best out of nrankable objects

Bruss, F. Thomas ; Louchard, Guy.
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. […]

Variance and Covariance of Several Simultaneous Outputs of a Markov Chain

Kropf, Sara.
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 […]

Automata in SageMath---Combinatorics meet Theoretical Computer Science

Heuberger, Clemens ; Krenn, Daniel ; Kropf, Sara.
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 […]

Persisting randomness in randomly growing discrete structures: graphs and search trees

Grübel, Rudolf.
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 […]

How often should you clean your room?

Martin, Kimball ; Shankar, Krishnan.
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 […]

On the Dynamics of Systems of Urns

Klonowski, Marek ; Cichoń, Jacek ; Kapelko, Rafał.
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 […]

Computing the number of h-edge spanning forests in complete bipartite graphs

Stones, Rebecca, .
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 […]

An algorithmic analysis of Flood-It and Free-Flood-It on graph powers

Souza, Uéverton dos Santos ; Protti, Fábio ; Silva, Maise, .
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 […]

Coupon collecting and transversals of hypergraphs

Wild, Marcel ; Janson, Svante ; Wagner, Stephan ; Laurie, Dirk.
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.

Connectivity for line-of-sight networks in higher dimensions

Devroye, Luc ; Farczadi, Linda.
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 […]

The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis

Louchard, Guy ; Prodinger, Helmut.
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 […]

The analysis of find and versions of it

Knof, Diether ; Roesler, Uwe.
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 […]

The Variance of the Profile in Digital Search Trees

Kazemi, Ramin ; Vahidi-Asl, Mohammad Q..
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 […]

Digital search trees with m trees: Level polynomials and insertion costs

Prodinger, Helmut.
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 […]

A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r

Kutzelnigg, Reinhard.
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 […]

Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System

Berthe, Valerie ; Imbert, Laurent.
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$, […]

On-line extensible bin packing with unequal bin sizes

Ye, Deshi ; Zhang, Guochuan.
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 […]

The location of the first maximum in the first sojourn of a Dyck path

Prodinger, Helmut.
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.

Convergence of some leader election algorithms

Janson, Svante ; Lavault, Christian ; Louchard, Guy.
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 […]

Analysis of some parameters for random nodes in priority trees

Panholzer, Alois.
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 […]

Waiting Time Distribution for Pattern Occurrence in a Constrained Sequence: an Embedding Markov Chain Approach

Nuel, Gregory.
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 […]

Waiting time distributions for pattern occurrence in a constrained sequence

Stefanov, Valeri T. ; Szpankowski, Wojciech.
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 […]

A combinatorial and probabilistic study of initial and end heights of descents in samples of geometrically distributed random variables and in permutations

Louchard, Guy ; Prodinger, Helmut.
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 […]

On the tileability of polygons with colored dominoes

Worman, Chris ; Yang, Boting.
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, […]

Arithmetics in β-numeration

Bernat, Julien.
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 […]

Asymptotic behaviour of a non-commutative rational series with a nonnegative linear representation

Dumas, Philippe ; Lipmaa, Helger ; Wallén, Johan.
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 […]

Note on the weighted internal path length of b-ary trees

Rüschendorf, Ludger ; Schopp, Eva-Maria.
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 tails for additive random recursive sequences

Rüschendorf, Ludger ; Schopp, Eva-Maria.
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 […]