Название: Algorithm Design: A Methodological Approach - 150 problems and detailed solutions
Автор: Patrick Bosc, Marc Guyomard, Laurent Miclet
Издательство: CRC Press
Год: 2023
Страниц: 820
Язык: английский
Формат: pdf (true)
Размер: 17.4 MB

A best-seller in its French edition, the construction of this book is original and its success in the French market demonstrates its appeal. It is based on three principles: 1. An organization of the chapters by families of algorithms : exhaustive search, divide and conquer, etc. At the contrary, there is no chapter only devoted to a systematic exposure of, say, algorithms on strings. Some of these will be found in different chapters. 2. For each family of algorithms, an introduction is given to the mathematical principles and the issues of a rigorous design, with one or two pedagogical examples. 3. For its most part, the book details 150 problems, spanning on seven families of algorithms. For each problem, a precise and progressive statement is given. More important, a complete solution is detailed, with respect to the design principles that have been presented ; often, some classical errors are pointed at. Roughly speaking, two thirds of the book are devoted to the detailed rational construction of the solutions.

This is a book about algorithmics, and its goal is to teach this field and to help instructors to teach it. Algorithmics is, as generally admitted, “the science and art of designing algorithms to solve a given problem, preferably in minimal time”. Consequently, this book aims at presenting efficient methods to design algorithms—mainly through examples.

It is structured according to two rules:

- Each chapter is devoted to a methodology of algorithm design, which can be applied to different data structures. For example, the chapter “Dynamic Programming” proposes problems on 2D arrays, on trees, on strings, as well as on graphs. As a matter of fact, some problems are proposed in two different chapters since they can be solved in different ways—which is particularly interesting to study. We have taken care for each problem to highlight different aspects of the methodologies: none of the 148 problems is just a rewriting of another one. The particular interest of each problem is shortly described at its beginning.

- Each chapter begins by an informal presentation on an example, then gives the technical bases of the methodology, and exposes a complete example. Then follows the main part, composed of detailed problems with their complete solution. Somewhat complex problems are tackled in a progressive manner in order to highlight the constructive process of the analysis leading to the solution. This solution is itself exhaustively detailed, concluding in programs written in pseudo-code. We do not give the coding in a specific programming language since the transcription from this pseudo-code into any usual one is generally straightforward. The correctness of all algorithms has been tested through code written by the authors.

Who must read it?
This is definitely not a book for beginners in computer science. Some knowledge of classical mathematics is required, as well as a solid initial formation in programming languages and data structures. It may be used by some classes of undergraduate students; however, it is obviously more suited for graduate studies, where it can be indicated as a textbook in algorithmics. It will also interest computer science professionals as a reference book.

The computer science instructors will find in this book a lot of useful material: the introduction of each chapter can be used as a reference for a lesson; the abundance of problems (along with their detailed solutions) will be an—almost—endless source for presenting to the students examples of methodical design. No problem is the exact rewriting of another one, and there is full freedom to transpose each of them in a different grounding.