An introduction to the analysis of algorithms. (Q5891518)

The book is concerned with a very important problem of the analysis of algorithm's correctness. As the problem is in general undecidable, the author wants to present an introduction to this important topic, the ideas behind programs and basic ways of such analysis.NEWLINENEWLINE The book begins ``with a chapter of preliminaries, containing the key ideas of induction and invariance, and the framework of pre/post-conditions and loop invariants. The author also proves the correctness of some classical algorithms, such as the integer division algorithm, and Euclid's procedure for computing the greatest common divisor of two numbers.''NEWLINENEWLINE Then three standard algorithm design techniques are presented: ``Greedy algorithms, dynamic programming and the divide and conquer paradigm. The author is concerned with correctness of algorithms, rather than, efficiency or the underlying data structures. For example, in the chapter on the greedy paradigm he explores in depth the idea of a promising partial solution, a powerful technique for proving the correctness of greedy algorithms. Online algorithms and competitive analysis as well as randomized algorithms with a section on cryptography, are included.''NEWLINENEWLINE ``Algorithms solve problems and many of the problems in this book fall under the category of optimization problems.''NEWLINENEWLINE The strong feature of the book are many examples: ``Most test understanding of the material, but many include coding in the Python programming language.'' ``One of the advantages of this programming language is that it is easy to start writing small snippets of code that work -- and most of the coding in this book falls into the ``small snippet'' category. The solutions to most problems are included in the ``Answers to selected problems'' at the end of each chapter.''NEWLINENEWLINE ``The intended audience for this book consists of undergraduate students in computer science and mathematics. The book is very self-contained, except for the Python course.''NEWLINENEWLINE Summing up, the book contains very nice introductory material for beginners in the area of correct algorithm's design.NEWLINENEWLINEFor a review of the first edition see [Zbl 1189.68182].