Lecture notes on bucket algorithms
This book is partially based on a graduate course on probability theory the author held at McGill. It covers the expected time analysis of various mostly simple-minded bucket algorithms for sorting and searching in one and higher dimensions. The analysis uses fairly advanced techniques from probability theory and is difficult to follow for the non-specialist. The point of the monograph is that simple-minded bucket algorithms are often superior in (expected) performance to occasionally complicated solutions with good and maybe optimal worst-case performance. The author's point is well taken, in particular because bucket algorithms tend to be simple to implement and thus have small overhead. Still, the comparison is not always fair since quite sophisticated worst-case algorithms can have very efficient implementations and are fast in all cases independent of the distribution of the data. The value of the lecture notes would have been much increased if the author had taken the time and effort to explain and introduce his analysis techniques for the non-specialist. After all, the book is apparently written mainly for programmers who rarely are fluent in the language and methods of probability theory. In particular, many common inequalities from probability theory are used without any attempt to properly explain or prove them.
- A provably fast linear-expected-time maxima-finding algorithm
- Intersections with random geometric objects
- Convex-hull algorithms: implementation, testing, and experimentation
- Process convergence for the complexity of radix selection on Markov sources
- How many maxima can there be?
- Records, the maximal layer, and uniform distributions in monotone sets
- An analytic approach to the asymptotic variance of trie statistics and related structures
- Unit theorems on algebraic tori
- A note on certain permutation groups in the infinite dimensional rotation group
- scientific article; zbMATH DE number 62475 (Why is no real title available?)
- On random cartesian trees
- scientific article; zbMATH DE number 1540682 (Why is no real title available?)
- A characterization of the Lévy Laplacian in terms of infinite dimensional rotation groups
- A PAC Approach to Application-Specific Algorithm Selection
- Maxima in hypercubes
- scientific article; zbMATH DE number 7650102 (Why is no real title available?)
- On some class number relations for Galois extensions
- Upper tail analysis of bucket sort and random tries
- Upper tail analysis of bucket sort and random tries
- Integrated empirical measures and generalizations of classical goodness-of-fit statistics
- An asymptotically optimal algorithm for generating bin cardinalities
This page was built for publication: Lecture notes on bucket algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787501)