This thesis is divided into four chapters. In the first chapter we describe the subtleties involved in probabilistically analyzing simple algorithms in computational geometry. We also work through a few easy examples of such analyses. The first example analyzes Quicksort, the second analyzes Quickhull, and the third analyzes interpoint distances between uniformly distributed points in hypercubes or hypertori. In the second chapter we present a simple but effective preprocessing algorithm for calculating convex hulls. The algorithm is short and intuitive. It does a fast linear scan through the points, identifying many which are not on the convex hull and can therefore be eliminated. We perform an exact analysis of this algorithm showing that, given n points distributed uniformly in the unit square, only about 8$\sqrt{n}$ of them remain after the preprocessing step: in higher dimensions only $c\sb{d}n\sp{1-1/d}$ will remain. We present the results of simulations comparing our mathematical analysis to reality. Finally, we end with a discussion of what distinguishes this algorithm from certain obvious variants. In the third chapter we analyze closest pair algorithms. First, we analyze a sweep-line closest-pair algorithm, one similar in spirit to Hoey and Shamos' divide and conquer algorithm for solving the same problem. Our result is that, given n points uniformly distributed in the unit square and then sorted, there is a six line algorithm that finds the closest pair in O(n) expected time. Moreover, this algorithm uses no complicated data structures. We then analyze a second algorithm, one that finds the closest pair using a modified version of Bentley and Papadimitriou's nearest neighbor projection algorithm. Our result, again, is that after the sorting stage, the linear scan stage of this new algorithm also finds the closest pair in O(n) expected time. The fourth chapter discussed the calculation of maxima. More specifically it analyzes a new heuristic, the Move-To-Front Algorithm, recently developed by Bentley, Clarkson and Levine. We prove mathematically that the Move-To-Front Algorithm is extremely efficient; on average it performs only one comparison per input point except on those in an asymptotically negligible subset.

Cited by 3

Probabilistic analysis of sorting algorithms

Dolenc, Martin · Repository of the University of Ljubljana (University of Ljubljana) · 2025

V delu si bomo ogledali, kako lahko s pomočjo verjetnosti analiziramo obnašanje sortirnih algoritmov in si ogledali rezultate analize za nekatere klasične sortirne algoritme.

Cited by 0Open access

Probabilistic analysis of tree algorithms

Hanène Mohamed, BOUGEROL, Philippe · OpenGrey (Institut de l'Information Scientifique et Technique) · 2007

Cette thèse est dédiée à l'étude d'une large classe d'algorithmes, appelés algorithmes en arbre. En utilisant une représentation probabiliste appropriée, le comportement asymptotique de tels algorithmes est analysé. L'approche unifie les études faites sur ces algorithmes ainsi que simplifie et généralise certains résultats établis dans le domaine.

Cited by 0

Probabilistic analysis of some search algorithms /

Jenn-Hwa Yu · OhioLink ETD Center (Ohio Library and Information Network) · 1990

Cited by 0Open access

Probabilistic analysis of numerical integration algorithms

Feng Gao · Journal of Complexity · 1991

Cited by 2

Probabilistic language analysis of weighted voting algorithms

Louise E. Moser, Vikas Kapur, P. M. Melliar‐Smith · 1990

We present a method of analyzing the performance of weighted voting algorithms in a fault-tolerant distributed system. In many distributed systems, some processors send messages more frequently than others and all processors share a common communication medium, such as an Ethernet. Typical fault-tolerant voting algorithms require that a certain minimum number of votes be collected from different processors. System performance is significantly affected by the time required to collect those votes. We formulate the problem of weighted voting in terms of probabilistic languages and then use the calculus of generating functions to compute the expected delay to collect that number of votes. An application of the method to a particular voting algorithm, the Total protocol, is given.

Cited by 3

Skip lists and probabilistic analysis of algorithms

Thomas Papadakis · 1993

This thesis is concerned with various forms of skip lists, and with probabilistic analyses of algorithms. We investigate three topics; one topic from each of these two areas, and another topic common to both of them. First, we consider Pugh's skip list. We derive exact and asymptotic expressions for the average search cost of a fixed key and of an average key. Our results improve previously known upper bounds of these two average search costs. We also derive exact and asymptotic expressions for the variance of the search cost for the largest key. Next, we propose several versions of deterministic skip lists. They all have guaranteed logarithmic search and update costs per operation, they lead to an interesting bridge structure between the original skip list and standard search trees, they are simpler to implement than standard balanced search trees, and our experimental results suggest that they are also competitive in terms of space and time. Finally, we consider the elastic-budget trie, a variant of the standard trie, in which each external node (bucket) has precisely as many key slots as the number of keys stored in it. We examine the number of buckets of each size, and we derive exact and asymptotic expressions for their average values, as well as asymptotic expressions for their variances and covariances under the closely related Poisson model of randomness. Our experimental results suggest that maintaining only two bucket sizes may be a very reasonable practical choice.

Cited by 26

Probabilistic Analysis of Random Extension-Rotation Algorithms

John H. Reif, Paul G. Spirakis · Defense Technical Information Center (DTIC) · 1981

We introduce a new random structure generalizing matroids. The random independence systems (RIS) allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs. We describe a randomized algorithm for efficiently constructing an independent set of fixed size in an instance of a random independence system. We provide a general method of analysis of the performance of this algorithm, which allows us to derive bounds on the mean, variance and all the moments of the time complexity of the algorithm. (Author)

Cited by 1

Probabilistic analysis and optimization of search algorithms

Dobromir P. Kralchev · Asian-European Journal of Mathematics · 2024

An interesting phenomenon about search algorithms is theoretically explained. Exponential optimization of running times has been achieved: the bigger the input size, the greater the acceleration. The optimization is equally applicable to exhaustive search, backtracking, and stochastic search.

Cited by 0

PROBABILISTIC ANALYSIS OF PACKING AND PARTITIONING ALGORITHMS

L. A. Shepp · Bulletin of the London Mathematical Society · 1993

By E. G. Coffman Jr and G. S. Lueker: 192 pp. £45.50, ISBN 0 471 53272 X (John Wiley, 1991).

Cited by 4

Probabilistic analysis of algorithms and data structures

Luc Devroye · Lecture notes in computer science · 1989

Cited by 1

Probabilistic Analysis of Disjoint Set Union Algorithms

Béla Bollobás, István Simon · SIAM Journal on Computing · 1993

A number of open questions are settled about the expected costs of two disjoint set Union and Find algorithms raised by Knuth and Schönhage [Theoret. Comput. Sci., 6 (1978), pp. 281–315]. This paper shows that the expected time of the Weighted Quick-Find (QFW) algorithm to perform $(n - 1)$ randomly chosen unions is $cn + o({n / {\log n}})$, where $c = 2.0847 \ldots $ . Through an observation of Tarjan and Van Leeuwen in [J. Assoc. Comput. Mach., 22 (1975), pp. 215–225] this implies linear time bounds to perform $O(n)$ unions and finds for a class of other union-find algorithms. It is also proved that the expected time of the Unweighted Quick-Find (QF) algorithm is ${{n^2 } / {8 + O(n(\log n)^2 )}}$. The expected costs of QFW and QF are analyzed when fewer than $(n - 1)$ unions are performed. Among other results, for QFW it is shown that the expected cost of $m = o(n)$ randomly chosen unions is $m(1 + o(1))$. If $m = {{\alpha n} / 2}$, where $\alpha \leqslant e^{ - 2} $, this cost is $m(1 + \epsilon (\alpha ) + o(1))$, where $\epsilon (\alpha ) \to 0$ as $\alpha \to 0$ and $\epsilon (e^{ - 2} ) \leqslant .026$. For QF, the expected cost of ${n / {2 - n^{{2 / 3}} }}(\log n)^{{2 / 3}} $ randomly chosen unions is $O(n\log n)$.

Cited by 8

A Statistical Analysis of Probabilistic Counting Algorithms

Peter Clifford, Ioana A. Cosma · Scandinavian Journal of Statistics · 2011

Abstract. This article considers the problem of cardinality estimation in data stream applications. We present a statistical analysis of probabilistic counting algorithms, focusing on two techniques that use pseudo‐random variates to form low‐dimensional data sketches. We apply conventional statistical methods to compare probabilistic algorithms based on storing either selected order statistics, or random projections. We derive estimators of the cardinality in both cases, and show that the maximal‐term estimator is recursively computable and has exponentially decreasing error bounds. Furthermore, we show that the estimators have comparable asymptotic efficiency, and explain this result by demonstrating an unexpected connection between the two approaches.

Cited by 28