×

Algorithmics of nonuniformity: tools and paradigms. (English) Zbl 1402.68004

Discrete Mathematics and its Applications. Boca Raton, FL: CRC Press (ISBN 978-1-4987-5071-4/hbk; 978-1-4987-5072-1/ebook). xix, 569 p. (2019).
This book s a unique collection of eleven chapters overviewing fundamental approaches in computer science from the angle of a non-uniform input. In the first chapter the authors lay out the general setup, introducing the mathematical/computational concepts used throughout the book, such as Turing machines, how to present algorithms in pseudocode and asymptotic notation. The second chapter focuses on algorithms related to counting; it commences with a description of generating functions and how these can be used to create special numbers. A detailed description of the combinatorial interpretation of such numbers (the Stirling numbers) is presented in the next section. The chapter concludes with other applications of these functions in probability theory and to determine the solutions of recurrences. In the third chapter the authors present elements of symbolic calculus focusing on admissible operations (the sum and product rules and combinatorial operations) followed by a series of applications supported with examples and exercises, including the composition of integers and tree counting. In the fourth chapter formal languages and automata are introduced, with an emphasis on regular languages, finite-state automata, and the link between them. Also included are examples of generating functions and their regular languages (i.e. word equations). Methods for counting regular languages and a discussion on the admissibility of solutions conclude the chapter.
In the fifth chapter the authors introduce notions of probabilities. Following an overview of random variables and characteristic functions, some classical inequalities (Boole, Chebyshev, Markov, Gauss, Schwarz) are introduced next. The chapter concludes with some classic results from probability theory, the central limit theorems, and the definition of martingales. The sixth chapter focuses on functional transforms, mainly the Mellin transforms and the methods of Poissonization applied on uniform and arbitrary distributions. In the seventh chapter the authors present the non-uniform Polya urn schemes. First, the classic urns are introduced. Next, different methods of ball activity (Polya-Eggenberger, Ehrenfest, Bagchi-Pal and triangular urns) are described through examples and exercises. The non-uniform Polya processes are also discussed.
In Chapter eight non-uniform data models are presented. The chapter commences with the notion of restricted permutations and a description of automata for such permutations (i.e., 1-away and 2-away). In the next sections random multisets and binary and digital search trees are presented (with a focus on optimal and near optimal searches). In the ninth chapter the authors present details of two established methods for sorting (the insertion sort and quicksort) applied on a non-uniform input. In the tenth chapter different aspects of recursive trees are discussed at large; following the description of uniform recursive trees, other types of trees, such as trees with vertex affinity proportional to age, recursive trees grown under the power of choice, block trees and Hoppe trees, are presented. For each of these, the depths of nodes and the characteristics of leaves are analysed in detail. Concluding the book, in the eleventh chapter, the authors present series-parallel graphs. Following approaches for enumerating binary series-parallel graphs, the order and the path lengths in these graphs are discussed in detail. Methods for graphs with unrestricted degrees, and nodes of small out-degrees end the chapter.
A particularity of the book that recommends it to a wide audience, spanning from undergraduates to established researchers, is the amount of theoretical detail included in each chapter and the impressive number exercises (for the latter, detailed solutions are presented at the end of the book). Although written mainly for a computing science audience, the thoroughness of examples make it accessible across sciences and endorse this work as the reliable starting point for understanding algorithms applicable to non-uniform inputs.

MSC:

68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68P05 Data structures
68P10 Searching and sorting
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68R05 Combinatorics in computer science
68R10 Graph theory (including graph drawing) in computer science
68W01 General topics in the theory of algorithms
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: Link