Sequential and parallel algorithms and data structures. The basic toolbox.

*(English)*Zbl 1445.68003
Cham: Springer (ISBN 978-3-030-25208-3/hbk; 978-3-030-25209-0/ebook). xv, 509 p. (2019).

The book under review is structured as a textbook overviewing a wide range of concepts, from basic, introductory ones to advanced ones. It comprises fourteen chapters, five appendices (with yet additional explanations on mathematical symbols and concepts, as well as basics of probability theory, on computer architecture aspects related to CPUs and RAM, on C++ implementations and the usage of the Message Passing Interface (MPI)). Also included is an extensive set of references that provide further guidance for these concepts.

The first chapter commences with introductory notions on integer arithmetic, focusing on addition and multiplication, and on their parallel implementation – the Karatsuba multiplication. Next (in Chapter two), the authors present the fundamental concepts that will form the basis of the theory and examples presented throughout the book, i.e., the asymptotic notation and the computing components of (sequential and parallel) pseudocode and algorithm analyses. Also included in this chapter are a brief overview of graphs and of the complexity classes P and NP.

The next four chapters present various concepts on lists. In the third chapter the focus is on the characteristics of arrays and linked lists. The processing of unbounded arrays and the use of amortised analyses are presented in detail. The features of stacks and queues are also included. In the fourth chapter the authors discuss hash tables and associative arrays, with an emphasis on hashing with chaining, universal hashing and hashing with linear probing; perfect hashing and parallel hashing are also introduced. In the following chapter the various sorting strategies are overviewed – simple sorting, merge-sort, quicksort, radix sort; the assessment of each of these approaches in the context of breaking the lower bound and adapting them to a parallel setup adds an extra layer of understanding. In the sixth chapter, priority queues are discussed (with a focus on binary heaps and parallel priority queues).

The next five chapters focus on graph approaches. The seventh chapter links the sorting strategies presented earlier to binary search trees (red-black trees and augmented search trees are presented in detail). In the eighth chapter more details on graph representations are presented, including the use of adjacency arrays for static graphs and lists for dynamic graphs. Next, breadth-first search and depth-first search, and their characteristics, are presented in detail. In the tenth chapter the authors focus on shortest paths algorithms, like Dijkstra’s algorithm for nonnegative edge costs, and the Bellman-Ford algorithm for arbitrary edge costs. Also included are a series of queries on shortest paths problems. The last one of the graph chapters (Chapter 11) presents minimum spanning trees; Kruskal’s algorithm, the union-find data structure and the Jarnik-Prim algorithm are presented in detail.

The last three chapters of the book focus on optimisation problems. Chapter 12 is built as an overview of optimisation approaches, offering summaries for linear programming, greedy methods, dynamic programming and evolutionary algorithms. Next, the authors present theoretical aspects of collective communication and computation, followed by a chapter on load-balancing approaches – the prefix sums, the master-worker scheme and randomised static load-balancing.

All chapters include numerous examples, applications, as well as implementation notes that guide the reader on the computational tasks. Also present are a series of historical notes and further findings that entice the reader to further explore the topic. The style of the book is accessible and is suitable for a wide range of audiences, from mathematicians and computer scientists to researchers from other fields who would like to use parallelised approaches in their research.

The first chapter commences with introductory notions on integer arithmetic, focusing on addition and multiplication, and on their parallel implementation – the Karatsuba multiplication. Next (in Chapter two), the authors present the fundamental concepts that will form the basis of the theory and examples presented throughout the book, i.e., the asymptotic notation and the computing components of (sequential and parallel) pseudocode and algorithm analyses. Also included in this chapter are a brief overview of graphs and of the complexity classes P and NP.

The next four chapters present various concepts on lists. In the third chapter the focus is on the characteristics of arrays and linked lists. The processing of unbounded arrays and the use of amortised analyses are presented in detail. The features of stacks and queues are also included. In the fourth chapter the authors discuss hash tables and associative arrays, with an emphasis on hashing with chaining, universal hashing and hashing with linear probing; perfect hashing and parallel hashing are also introduced. In the following chapter the various sorting strategies are overviewed – simple sorting, merge-sort, quicksort, radix sort; the assessment of each of these approaches in the context of breaking the lower bound and adapting them to a parallel setup adds an extra layer of understanding. In the sixth chapter, priority queues are discussed (with a focus on binary heaps and parallel priority queues).

The next five chapters focus on graph approaches. The seventh chapter links the sorting strategies presented earlier to binary search trees (red-black trees and augmented search trees are presented in detail). In the eighth chapter more details on graph representations are presented, including the use of adjacency arrays for static graphs and lists for dynamic graphs. Next, breadth-first search and depth-first search, and their characteristics, are presented in detail. In the tenth chapter the authors focus on shortest paths algorithms, like Dijkstra’s algorithm for nonnegative edge costs, and the Bellman-Ford algorithm for arbitrary edge costs. Also included are a series of queries on shortest paths problems. The last one of the graph chapters (Chapter 11) presents minimum spanning trees; Kruskal’s algorithm, the union-find data structure and the Jarnik-Prim algorithm are presented in detail.

The last three chapters of the book focus on optimisation problems. Chapter 12 is built as an overview of optimisation approaches, offering summaries for linear programming, greedy methods, dynamic programming and evolutionary algorithms. Next, the authors present theoretical aspects of collective communication and computation, followed by a chapter on load-balancing approaches – the prefix sums, the master-worker scheme and randomised static load-balancing.

All chapters include numerous examples, applications, as well as implementation notes that guide the reader on the computational tasks. Also present are a series of historical notes and further findings that entice the reader to further explore the topic. The style of the book is accessible and is suitable for a wide range of audiences, from mathematicians and computer scientists to researchers from other fields who would like to use parallelised approaches in their research.

Reviewer: Irina Ioana Mohorianu (Oxford)

##### MSC:

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

68P05 | Data structures |

68P10 | Searching and sorting |

68Wxx | Algorithms in computer science |