Lecture notes on bucket algorithms

From MaRDI portal





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.











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)