Comprehensiveness rating: 5 read less
It does a very thorough job of describing data structures for stacks, queues, lists, sets, and “sortedSets” — the latter not exactly a standard mathematical structure, but quite a useful one for many algorithms. It also has chapters on Priority queues, sorting, graph representation and traversal, tries, and B-trees. The treatment of the basic data structures for lists and sets is unusually comprehensive, covering not just linear lists but also skiplists, hash tables, and various kinds of tree. The chapter on hashing covers not just hash tables, but also the construction of hash functions, a topic that is often omitted in texts.
It also contains some introductory material on asymptotic notation, randomization and probability. My feeling that this material would be a useful refresher for a student (or a professor!) who hadn’t used this kind of mathematics for a while, but that it would by itself be inadequate as an introduction. This may be a reflection on the different levels of math education expected at a university in Canada vs on in the USA.
Accuracy rating: 4
I didn’t find any errors in the book, and feel that it is accurate. However, I
did not read all of the later chapters in detail, and certainly did not check
the proofs. Its treatment of Quicksort is much better than that of many
algorithms books, since it assumes from the start (as did Hoare in the original
papers) that the pivot must be chosen randomly. I was a little disappointed,
though, to see that one other feature of Quicksort, which I consider obligatory,
was omitted — the double-ended traversal in the partition algorithm,which reduces
the number of swaps by roughly half compared to a single-ended traversal. This
can’t be considered a bug, though, because the book does not include an analysis
of the number of swaps, only of the number of comparisons, even though the
latter is a much less expensive operation.
Relevance/Longevity rating: 4
This material is pretty stable. The book does not include some of the more
recent development, such as dual-pivot Quicksort, but the topic of data
structures moves so quickly that it would be impossible to include every new
development. In any case, this would not be appropriate in a textbook.
Clarity rating: 4
The text is written in lucid, accessible prose. Sometimes I was left wanting a
little more context. For example, in the discussion of multiplicative hashing,
a couple of sentences describing the goal (mixing up the bits of the input) and
the mechanism (selecting some of the “middle” bits of the product of the input
and a randomly-chosen constant) would have been useful, as a prelude to the
detailed discussion of the mechanism.
Consistency rating: 5
With a very few exceptions, the text is internally consistent in terms of
terminology and framework. There is just one place where I noticed the
consistency breaking down, in the section on random Binary Search Trees, where
there seems to be some confusion between _element n_ and the element with _rank n_.
Modularity rating: 4
All the chapters depend the interfaces, computational model and analysis techniques defined in Chapter 1. Apart from that, the other chapters are largely self-contained. This is about as good as could be expected.
However, two of the names given to the interfaces in chapter 1 are obscure. Everyone knows what a Queue and a Stack are, but what's an SSet? Every time I came back to the book after working on something else, I had to remind myself what a USet and and SSet were. This is so unnecessary. It turns out that a USet is just a mutable Set, while an SSet is a mutable Sorted Set. Using the slightly longer names would make this book much more useful as a reference.
Organization/Structure/Flow rating: 5
Generally, the book is very well organized, working form simple and straightforward (not no necessarily fast) data structures to complex one that have better amortized performance. By only objection is to chapter 13, which is titled Data Structures for Integers,
but which deals with Tries. I tend to think of Tries as a data structure for variable-length strings, although they can certainly be used for integers too.
Interface rating: 5
It's a very nice looking text.
Grammatical Errors rating: 5
Excellent! And I'm a picky reviewer.
Cultural Relevance rating: 5
The text is not culturally insensitive or offensive in any way that I observed.
I enjoyed reading it — this is important.