REVIEW - Algorithms: A Functional Programming Approach (second edition)

Title:

Algorithms: A Functional Programming Approach (second edition)

Author:

Addison-Wesley

ISBN:

0201596040

Publisher:

Addison-Wesley ()

Pages:

232

Reviewer:

Colin Paul Gloster

Reviewed:

February 2011

Rating:

★★★☆☆

"Computer Algorithms: Introduction to Design & Analysis" and "Introduction to Algorithms" are normal textbooks on general-purpose algorithms for a wide variety of problems. "Algorithms: A Functional Programming Approach" is also a general-purpose book, but the choice of Haskell and the small page count (arising from fewer topics and shallow coverage instead of any supposed advantage of Haskell) make it obviously different at a first glance. However, a surprising difference which became apparent after I started reading it is that Rabhi and Lapalme concentrated on space complexity instead of time complexity. Bearing that major drawback in mind, it is a fairly good book, though it is yet another unconvincing attempt at functional advocacy, and it is overpriced.

As for the other two books, they are big as books on algorithms should be. More algorithms are covered (or at least mentioned) in "Introduction to Algorithms", but there are more details in "Computer Algorithms: Introduction to Design & Analysis" for the algorithms covered therein. (Fewer problems are covered in "Algorithms in C++: Parts 1-4: Fundamentals; Data Structures; Sorting; and Searching" by Robert Sedgewick and Christopher J. Van Wyk, but at even greater depth.)

Cormen et al. used pseudocode with various mathematical symbols such as arrows which are not on normal keyboards (unless old APL keyboards are more common than I thought), whereas Baase et al. used a pseudo-language based on what used to be Java. Their preconditions and postconditions in Javadoc comments indicate that Eiffel would have been better but Java's marketing was not mentioned as one of the factors contributing to the choice to use Java. A lot more recursion and fewer overwriting assignments were used than in other imperative programs, but not to an extent qualifying as functional programming. Sometimes they used zero-based indexing, sometimes they used one-based indexing: Ada would have been better than Java.

Baase et al. suggested "Accelerated Heapsort may become the sorting method of choice" but I do not believe that this has happened. They waited until Page 650 to warn "With currently available compilers, a program written in Java runs more slowly than a program written in C." They recommended converting exceptions into errors because handling exceptions would be necessary but handling errors are merely optional.

The books under review are not particularly biased towards a specific application domain, but "Introduction to Algorithms" has a few examples of how algorithms are useful for electronic engineering and it also has a chapter on arithmetic hardware.

The books under review mainly deal with sequential algorithms for tractable problems. The chapter by Baase and Van Gelder on parallel algorithms conveyed the point that the relative merits of algorithms changes if they are to be run on uniprocessors or multiprocessors better than the other books. Instead of plainly revealing important points in the bodies of the chapters, Cormen et al. left too much to exercises. Their chapter on dynamic programming is better than the one by Baase and Van Gelder.

These books are fairly old so smoothed analysis is not in them.

Only a very small selection of numerical methods is presented in these books, but "Introduction to Algorithms" and "Computer Algorithms: Introduction to Design & Analysis" are much closer to the state of the art on multiplying dense matrices than every book dedicated to numerics which I have read.


Book cover image courtesy of Open Library.