Implementing Useful Algorithms in C++

Programmers use algorithms and data structures all the time, usually through numerous available APIs. Ideally an algorithm is correct, easy to understand, applicable to many problems, efficient, and free of intellectual property claims. This book covers algorithms and data structures learned in an algorithms class and many that aren't, including statistical algorithms, external memory algorithms, numerical methods, optimization, string algorithms, and data compression.

About a fourth of the book is devoted to machine learning. There is much more theory than in the rest of the book because in machine learning relevant theory is more practical than algorithms. New learning algorithms are proposed often, and it's easy to get lost without understanding how learning actually works. In particular, getting comfortable with the concept of estimation error substantially improves the ability to reason about statistical algorithms.

Another fourth is about numerical algorithms. Separate chapters cover matrix algorithms (such as eigenvalue calculation for spectral clustering), working with functions (integration, root finding, etc.), and optimization (both continuous and convex).

Expect to learn something new in every chapter. Many topics appear only in specialized books and papers, including collections of random number generators and hash functions for various use cases, priority queues that allow random access for applications like Djikstra's shortest path algorithm, the simplex method for linear programming, efficient dictionaries for variable-length keys, Monte Carlo and bootstrap methods for statistical computing, top-performing learning algorithms such as random forest, etc. One of the goals of the book is answering all questions you might have had since taking an algorithms class.

Algorithm descriptions have tested C++ code, illustrations, performance analysis, and suggestions for optimizations and extensions. Still, the book is advanced, requiring some algorithmic maturity. After working through it, you will know more about algorithms and machine learning than before, even if you are already an expert. This is the book the author wishes he had when he started studying algorithms.