Open Data Structures: An Introduction

Reviewed by Joseph Jess, Faculty, Linn-Benton Community College on 1/14/20

Comprehensiveness rating: 5 see less

The text covers all areas I would expect to see in an introduction to data structures (lists, trees, hash tables, graphs, supporting searching and sorting algorithms for relevant structures, and plenty of complexity analysis) with a variety of variations on the structures and some reasoning as to why we might want to use these variations. The table of contents and term-based index have enough detail especially considering the organized structure of the book.

Content Accuracy rating: 4

The contents are accurate, I found no obvious errors, and at least mentions and gives brief examples of the background information needed to be most successful with the materials; though having some explanation on some of the common proof techniques used with data structures that we use could be beneficial as well (there is some mention of this in the mathematical background section but not much of the reasoning behind why we care about this analysis).

Relevance/Longevity rating: 5

The content is very relevant for an introduction to data structures, needing to cover the simpler version of these structures and then provide a few variations from the many decades of basic materials covered; this will hopefully show students that this is an area that is still being researched heavily. Updating the basics I expect to be rare, and a perfect starting point for using these structures in other related areas while allowing new developments (and far far more detailed than some of these basic structures) to be covered in a separate text or other resource.

Clarity rating: 4

The text is written in prose accessible to someone with perhaps a year of academic courses in computer science, but does lean somewhat on someone having solved problems either programmatically or having a good deal of mathematical background. The jargon is light and well explained, though their variables for the code examples could be greatly improved...

Consistency rating: 5

The book is very consistent with regards to terminology and framework, I greatly appreciate the regular use of diagrams showing the sequence of actions for an operation to complete (something I frequently draw out on a whiteboard or digital tablet for students).

Modularity rating: 4

The text is readily divisible into smaller reading sections, though you would want to be careful about jumping beyond certain sections before knowing someone had taken in some of the key concepts from a simpler set of structures (perhaps broken into the sections on lists, then hashes and trees, then graphs and sorting, then structures for integers and external memory searching), since they sometimes build on a key concept (such as a simple linked-list node, then a binary tree node, then a more general node).

Organization/Structure/Flow rating: 5

The topics are in a logical order, and so long as someone pauses to ask what the key behaviors and components of a structure are should then be able to see the next section adding either a variation on what we already have access to or roughly one new feature to some of the components we have access to.

Interface rating: 5

The contents look great!

Grammatical Errors rating: 5

The English contents follow English grammar rules well, and the simplified code examples should be easily followed by someone having worked with a C-based language or a good deal of mathematics before.

Cultural Relevance rating: 5

The text is not culturally insensitive or offensive to me; though it does not make use of virtually any examples or variety of race, ethnicity, or background.

Comments

I plan to use this as a supporting text for my own data structures course with the many explanations for why we study each structure and why we care about each section we analyze or implement ourselves; with it covering all the major topics that I do in class and having variations that I do not bring up in class due to time constraints.

Reviewed by Breeann Flesch, Associate Professor of Computer Science, Western Oregon University on 2/25/19

Comprehensiveness rating: 5 see less

This book covers all of the topics typical in an introductory data structures class (complexity, sorts, stacks, queues, binary search trees, heaps, hash tables, etc).

Content Accuracy rating: 5

The book is thorough and accurate, including relevant mathematical topics for background information.

Relevance/Longevity rating: 5

Since this course covers the foundations of computer science, it is likely to be relevant for a long time.

Clarity rating: 5

The book has lots of examples and pictures. The code examples are based on Java, but have been simplified enough to consider them language-agnostic pseudocode.

Consistency rating: 4

The book's definitions and notation are consistent throughout.

Modularity rating: 4

It would be easy to assign smaller chunks for scaffolding. However, many topics do build upon previous sections, so it may be difficult to jump around or skip sections.

Organization/Structure/Flow rating: 5

The book is organized well, making sure that topics build in a logical order.

Interface rating: 5

The entire book seemed to display well with my pdf reader.

Grammatical Errors rating: 4

The text contains few grammatical errors.

Cultural Relevance rating: 5

This book is as culturally sensitive as makes sense for a data structures text.

Comments

Overall, this book is comprehensive and accurate. I will use it for my data structure classes in the future.

Reviewed by Andrew Black, Professor, Portland State University on 8/21/16

Comprehensiveness rating: 5 see 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.

Content 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.

Comments

I enjoyed reading it — this is important.