[CR has previously published a review of this book (see Review CR139890). The author of the book has written a rebuttal to the review (see Review CR140550), and the reviewer has written a re-rebuttal.]

I would like to thank the author for his response to my review. While I do stand corrected in the matter of the few examples of pseudocode that he has pointed out, I submit that the main thrust of my claim---namely, that the book presents algorithms without resorting to the device of pseudocode---is essentially correct. The author is of course entitled to his expressed opinion that pseudocode is not always the most effective way to present algorithms, and others [1] do as he has done by presenting algorithms without pseudocode.

While the book offers some (arguably informal) analyses of program complexity in some cases, I find no proof of program correctness in the book---chapter 5 by A. K. Yan and B. R. Donald is titled “Principal Components Analysis [PCA], Residual Dipolar Couplings [RDCs], and Their Relationship in NMR Structural Biology,” and it promises, on page 27, that the reader “will understand the fundamentals of RDCs, which are important in structural biology, and know the foundations of PCA, one of the most important algorithms in computational science and applied statistics.” While surely this is quite a good thing, it is hardly what computer scientists from the Floyd-Hoare school would consider as a proof of correctness. Proofs of program correctness were vigorously argued for by Lamport decades ago, when he wrote, “The ACM should require that programmers convince us of the correctness of the programs that they publish, just as mathematicians must convince one another of the correctness of their theorems” [2].

I have not said, and should not be understood to mean, that there is no mathematical content in the book, such as the examples the author has cited; the propositions and so forth that he mentions are mathematical results (and certainly quite unobjectionable as such), but they are not proofs of correctness of specific algorithms--such often involve invariants, as well as lemmas and theorems asserting specific properties of the programs such as liveness and progress. These are not to be seen in any of the examples given---for instance, chapter 50 is definitely not, I firmly submit, devoted to any proof of program correctness, as also indicated by the author himself in the book: “We have described an algorithm for computing all the homology groups of a triangulation” (page 411), and “This chapter provided an introduction to some aspects of computational topology and protein structure” (page 412). The only discussion of complexity of the proposed algorithm is on page 409, which says:

All of the steps in the algorithm given in Section 50.5.3 are essentially linear-time or quadratic-time operations except the reduction algorithm. The time R (n) required by the reduction algorithm (Section 5.50.3), in fact, dominates the computation of homology type, which can clearly be done in time O (D (n² + R (n))). The worst-case analysis of the algorithm indicates that it could run in doubly exponential time, due to the potential growth of the integer coefficients. While worst-case bounds for the reduction algorithm are very poor, the algorithm is straightforward to implement and in practice it runs very efficiently for a geometric object (such as a protein) that is embedded in three-dimensional Euclidean space.

This is at best a casual discussion of complexity, but hardly a rigorous analysis of it, and does not at all address program correctness. Similarly, this is the case elsewhere.