##
**Algorithmics. Theory and practice.**
*(English)*
Zbl 0643.68003

London etc.: Prentice-Hall. XVI, 361 p. $ 29.95 (1988).

The situation with books on algorithms is similar to a symphony developed on a theme with variations basis. Algorithms represent a generous theme which allows many interesting variations although not very different from one another. The book under review is still another excellent account on algorithms which aims to teach the reader a style of producing good algorithms in whatever field of application they may be required. Thus the material is organized around the main paradigms on designing efficient algorithms with a good amount of concern dedicated to their analysis. The concrete examples are taken from as various domains as optimization, linear algebra, cryptography, operations research, symbolic computation, artificial intelligence, numerical analysis, puzzles, game theory and others. Usually a naive brute-force algorithm is transformed into a number of successively better algorithms, each stage in the process illustrating a facet of the exemplified paradigm.

The book consists of three parts. The first one (Chapter 1: Preliminaries, Chapter 2: Analysing the efficiency of algorithms) is essential to understanding the rest of the book, since it introduces the main technical tools used throughout the material. Thus Chapter 1 describes the language used for presenting algorithms (the usual Pascal- like pseudocode), the basic data structures, the measures by which the efficiency of algorithms are analyzed, and Chapter 2 introduces the asymptotic notation and exhibits the basic mathematical techniques for solving recurrences.

The second part (Chapter 3: Greedy algorithms, Chapter 4: Divide and conquer, Chapter 5: Dynamic programming, Chapter 6: Exploring graphs, Chapter 7: Preconditioning and precomputation) concentrates on the principles used to design and analyze efficient algorithms. By the help of the above mentioned stepwise refinement method, the authors do not miss the opportunity to present a good number of ingenious classical algorithms (the algorithms that every cultivated computer science student should know). The following list is not exhaustive: Kruskal’s algorithm for constructing the minimal spanning tree, Dijkstra’s algorithms for computing the shortest paths in a graph, binary searching, quicksort, the public-key cryptographic protocol, Strassen’s method for matrix multiplication, the Knuth-Morris-Pratt and Boyer-Moore algorithms for string searching.

The third part consists of three independent chapters having a more advanced character. Chapter 8 is devoted to probabilistic algorithms, classified in four groups: numerical, Las Vegas, Monte Carlo and Sherwood. The last group (whose name comes from the Robin Hood’s legend) deserves a special mention since it appears here for the first time. It consists of the algorithms that choose randomly some involved elements (for example the pivot in the quicksort), thus realizing a procedure whose run time does not depend on the specific instance to which it is applied. In this way there is no worst-case but there may be a worst execution. This chapter also offers an elegant approach to some arithmetical problems usually appearing in cryptography: factoring an integer, primality testing or calculating the square root modulo p. Chapter 9: Transformations of the domain, presents the fast Fourier transformation and its use in multiplying polynomials or large integers. Finally, Chapter 10: Introduction to complexity, describes some polynomial (in fact linear) time reducing among diverse problems occurring in arithmetic or graph theory culminating with a short exhibition of the theory of NP-completeness.

The book is intended as a textbook for an upper-level undergraduate or a lower level graduate course in algorithmics. Almost 500 exercises are dispersed throughout the text, most of them forming an integral part of the text. All the chapters are accompanied by historical notes and advice for further reading. The book is written in a clear and stimulating style and a diligent even experienced reader could gain from it many valuable insights concerning algorithms and their analysis.

The book consists of three parts. The first one (Chapter 1: Preliminaries, Chapter 2: Analysing the efficiency of algorithms) is essential to understanding the rest of the book, since it introduces the main technical tools used throughout the material. Thus Chapter 1 describes the language used for presenting algorithms (the usual Pascal- like pseudocode), the basic data structures, the measures by which the efficiency of algorithms are analyzed, and Chapter 2 introduces the asymptotic notation and exhibits the basic mathematical techniques for solving recurrences.

The second part (Chapter 3: Greedy algorithms, Chapter 4: Divide and conquer, Chapter 5: Dynamic programming, Chapter 6: Exploring graphs, Chapter 7: Preconditioning and precomputation) concentrates on the principles used to design and analyze efficient algorithms. By the help of the above mentioned stepwise refinement method, the authors do not miss the opportunity to present a good number of ingenious classical algorithms (the algorithms that every cultivated computer science student should know). The following list is not exhaustive: Kruskal’s algorithm for constructing the minimal spanning tree, Dijkstra’s algorithms for computing the shortest paths in a graph, binary searching, quicksort, the public-key cryptographic protocol, Strassen’s method for matrix multiplication, the Knuth-Morris-Pratt and Boyer-Moore algorithms for string searching.

The third part consists of three independent chapters having a more advanced character. Chapter 8 is devoted to probabilistic algorithms, classified in four groups: numerical, Las Vegas, Monte Carlo and Sherwood. The last group (whose name comes from the Robin Hood’s legend) deserves a special mention since it appears here for the first time. It consists of the algorithms that choose randomly some involved elements (for example the pivot in the quicksort), thus realizing a procedure whose run time does not depend on the specific instance to which it is applied. In this way there is no worst-case but there may be a worst execution. This chapter also offers an elegant approach to some arithmetical problems usually appearing in cryptography: factoring an integer, primality testing or calculating the square root modulo p. Chapter 9: Transformations of the domain, presents the fast Fourier transformation and its use in multiplying polynomials or large integers. Finally, Chapter 10: Introduction to complexity, describes some polynomial (in fact linear) time reducing among diverse problems occurring in arithmetic or graph theory culminating with a short exhibition of the theory of NP-completeness.

The book is intended as a textbook for an upper-level undergraduate or a lower level graduate course in algorithmics. Almost 500 exercises are dispersed throughout the text, most of them forming an integral part of the text. All the chapters are accompanied by historical notes and advice for further reading. The book is written in a clear and stimulating style and a diligent even experienced reader could gain from it many valuable insights concerning algorithms and their analysis.

Reviewer: M.Zimand

### MSC:

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

68W99 | Algorithms in computer science |

68Q25 | Analysis of algorithms and problem complexity |

68P10 | Searching and sorting |

68R10 | Graph theory (including graph drawing) in computer science |

94A60 | Cryptography |

11-04 | Software, source code, etc. for problems pertaining to number theory |

05-04 | Software, source code, etc. for problems pertaining to combinatorics |