Knuth D.E. The Art of Computer Programming: Volume 4B. Combinatorial Algorithms. Part 2

Addison-Wesley Professional, 2022. — 733 p. — ISBN 0201038064.The Art of Computer Programming is Knuth's multivolume analysis of algorithms. With the addition of this new volume, it continues to be the definitive description of classical computer science. Volume 4B, the sequel to Volume 4A, extends Knuth's exploration of combinatorial algorithms. These algorithms are of keen interest to software designers because "... a single good idea can save years or even centuries of computer time." The book begins with coverage of Backtrack Programming, together with a set of data structures whose links perform "delightful dances" and are ideally suited to this domain. New techniques for important applications such as optimum partitioning and layout are thereby developed. Knuth's writing is playful, and he includes dozens of puzzles to illustrate the algorithms and techniques, ranging from popular classics like edge-matching to more recent crazes like Sudoku. Recreational mathematicians and computer scientists will not be disappointed ! In the second half of the book, Knuth addresses Satisfiability, one of the most fundamental problems in all of computer science. Innovative techniques developed at the beginning of the twenty-first century have led to game-changing applications, for such things as optimum scheduling, circuit design, and hardware verification. Thanks to these tools, computers are able to solve practical problems involving millions of variables that only a few years ago were regarded as hopeless. The Mathematical Preliminaries Redux section of the book is a special treat, which presents basic techniques of probability theory that have become prominent since the original "preliminaries" were discussed in Volume 1. As in every volume of this remarkable series, the book includes hundreds of exercises that employ Knuth's ingenious rating system, making it easy for readers of varying degrees of mathematical training to find challenges suitable to them. Detailed answers are provided to facilitate self-study.Preface
A note on references
A note on notations
Notes on the Exercises
Exercises
Contents
Mathematical Preliminaries Redux
Inequalities
Martingales
Tail inequalities from martingales
Applications
Statements that are almost sure, or even quite sure
Exercises
Combinatorial Searching
Answers to Exercises
Appendices:
Tables of Numerical Quantities
Index to Notations
Index to Algorithms and Theorems
Index to Combinatorial Problems
Answers to Puzzles in the Answers
Index and Glossary
Code SnippetsTrue PDF