Algorithms from THE BOOK

This is a survey and cookbook of important algorithms in mathematics and computer science, intended as a text for a semester course at the upper-level undergraduate or beginning graduate level. The present book is titled in homage to Paul Erdős’s idea of The Book, a book maintained by God containing all the most beautiful mathematical proofs (and to its earthly representation, Aigner and Ziegler’s Proofs from THE BOOK). It has a different nature, though, as it covers the most important and influential algorithms rather than the most beautiful ones.

 

The strength of the book is the descriptions of the many applications of the algorithms, rather than the coverage of the algorithms themselves. The exposition is also especially clear.

 

Each chapter deals with a different class of algorithms, such as sorting, and most of each chapter deals with a summary of applications and some actual code (in the Julia language) for the algorithms of interest. The applications given cover a wide range of disciplines. There’s also a brief summary of the ideas behind each algorithm, and often a discussion of the strengths and weaknesses of competing algorithms. The book omits proofs of correctness, analysis of numerical errors, and complexity analysis. It usually quotes the complexity order of each algorithm, including average and worst cases. This is not a proofs book, although it does state and prove some theorems. Each chapter has numerous exercises. Most are challenging and involve writing and testing the code for related algorithms. There’s a concise appendix that covers most of the mathematical knowledge needed to read the book.

 

The algorithms chosen are slanted towards linear algebra and statistics, but it does cover all sorts of algorithms including discrete problems such as primality testing in number theory, sorting and searching, and shortest paths in graphs.  The author sometimes seems to feel conflicted about how much detail to show. He notes that there are excellent libraries available for things such as linear algebra, statistics, and eigenvalues, much better than the student could devise by himself. On the other hand, the author (and I) feel that students should understand something about the workings of the algorithms they use.

 

The publisher’s web site offers a free download of all the Julia code used in the book. Having actual code rather than pseudocode is a plus because the students can experiment with the algorithms and tinker with their operation.  The introductory book to beat in this field is still Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms. The latter book is about seven times as long as this one and covers a wider variety of material. Its main advantage over the present book is that it includes correctness proofs and complexity analysis. On the downside, it has pseudocode rather than executable code. Both books are good choices, although I think for different audiences. I think the present book fits better for an engineering audience, with the other one better for computer science and mathematics.

---

 

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His personal web site is allenstenger.com. His mathematical interests are number theory and classical analysis.