Programming contests typically ask teams of programmers to develop solutions to several posed problems in a limited amount of time. Knowledge of algorithms and the techniques for implementing those algorithms efficiently are critical for success, as is determining when a problem is an instance of, or can be reduced to, a particular algorithm. Competitive programming in Python aims to provide readers with the necessary understanding of algorithms and methods for implementing algorithms, to enable winning programming contests.
Chapter 1 begins with a brief discussion of programming competitions. The chapter then gives a brief introduction and overview of Python. This is not really intended for someone new to Python, but does serve as a reminder to those familiar with Python of some of the key constructs used in the book’s Python code. Other sections briefly discuss complexity, abstract types, and some common techniques used in the remainder of the book (such as sorting, greedy algorithms, and dynamic programming).
Chapters 2 through 15 present the algorithms grouped by topic. Topics covered include string processing, sequences, arrays, intervals, graphs, cycles in graphs, shortest paths, matching and flows, trees, sets, points and polygons, rectangles, numbers and matrices, and exhaustive search. Some of the classic algorithms covered are the stable marriage problem, Huffman coding, Eulerian tour, shortest path, traveling salesman, fast exponentiation, and so on. But there are also lesser known algorithms and techniques, such as “dancing links” for the exact cover problem and Fenwick trees.
Generally, the algorithm is briefly explained and its performance indicated. Python code is often (but not always) included. Sometimes multiple implementations of an algorithm are included when the performance of the simple case can be improved. In some cases, informal proofs or arguments of the correctness of the algorithm or its performance are given. A few hints for competition are interspersed in relevant places.
The final chapter includes a few final hints and several references for further work. A three-page reference section at the end collects 53 references to some of the algorithms discussed. A companion website (https://tryalgo.org) contains links to all the Python source code shown in the book, as well as to suggested problems and solutions. For the cases I checked, the code for the algorithms appeared to match that given in the book. In some cases, test code and test cases are also included. One test that I ran (test code for computing primes using the sieve of Eratosthenes) had an error that resulted in a divide by zero exception. In computing, the ratio of execution times for two implementations of the code ignored the fact that the times could be equal, resulting in a difference of zero that was used as a divisor.
While the subtitle claims 128 algorithms are included, this may not be meant literally. The algorithms are not numbered or listed in any fashion, and it’s not clear what is actually counted as an algorithm. Are only those for which code is presented in one of the figures counted? Or does it include other cases, where variants are only described in the text, sometimes very briefly? My counting in various ways resulted in somewhere from 90 to 122.
One pet peeve of mine: the inadequacy of the meager five-page index. It does not include many topics or the appearances of topics in the text, and both omits some references and gives wrong citations for others.
Overall, the book does provide a good and concise description of many useful algorithms, as well as the actual implementation of those algorithms in Python. It should be useful to its intended audience of programming competitors, anyone wanting a refresher on common algorithms, or those interested in Python programming. But of course there are no guarantees that readers will win programming contests as a result of reading this book--your competitors may have read it, too!
More reviews about this item: Amazon