Bruce Weide

Statistical Methods in Algorithm Design and Analysis Degree Type: Ph.D. in Computer Science
Advisor(s): Michael Shamos
Graduated: May 1979

Abstract:

The use of statistical methods in the design and analysis of discrete algorithms is explored. Among the design tools are randomization, ranking, sampling and subsampling, density estimation, and 'cell' or 'bucket' techniques. The analysis techniques include those based on the design methods as well as the use of stochastic convergence concepts and order statistics. The introductory chapter contains a literature survey and background material on probability theory.

In Chapter 2, probabilistic approximation algorithms are discussed with the goal of exposing and correcting some oversights in previous work. Some advantages of the proposed solution to the problems encountered are the introduction of a model for dealing with random problems, and a set of methods for analyzing the probabilistic behavior of approximation algorithms which permit consideration of fairly complex algorithms in which there are dependencies among the random variables in question.

Chapter 3 contains many useful design and analysis tools such as those mentioned above, and several examples of the uses of the methods. Algorithms which run in linear expected time for a wide range of probabilistic assumptions about their inputs are given for problems ranging from sorting to finding all nearest neighbors in a point set in k dimensions. Empirical results are presented which indicate that the sorting algorithm, Binsort, is a good alternative to Quicksort under most conditions.

Finally, Chapter 4 describes the uses of results from order statistics to analyze greedy algorithms and to investigate the behavior of parallel algorithms. Among the results reported here are general theorems regarding the distribution of solution values for optimization problems on weighted graphs.

Thesis Committee:
Michael Shamos (Chair)

Joseph Traub, Head, Computer Science Department