Open Data Structures: An Introduction
Pat Morin, Carleton University
Pub Date: 2013
ISBN 13: 978-1-9273563-8-8
Publisher: Athabasca University Press
Read This Book
Conditions of Use
It does a very thorough job of describing data structures for stacks, queues, lists, sets, and “sortedSets” — the latter not exactly a standard read more
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.
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.
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.
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.
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_.
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.
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.
It's a very nice looking text.
Excellent! And I'm a picky reviewer.
The text is not culturally insensitive or offensive in any way that I observed.
I enjoyed reading it — this is important.
Table of Contents
- Chapter 1. Introduction
- Chapter 2. Array-Based Lists
- Chapter 3. Linked Lists
- Chapter 4. Skiplists
- Chapter 5. Hash Tables
- Chapter 6. Binary Trees
- Chapter 7. Random Binary Search Trees
- Chapter 8. Scapegoat Trees
- Chapter 9. Red-Black Trees
- Chapter 10. Heaps
- Chapter 11. Sorting Algorithms
- Chapter 12. Graphs
- Chapter 13. Data Structures for Integers
- Chapter 14. External Memory Searching
About the Book
Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Focusing on a mathematically rigorous approach that is fast, practical, and efficient, Morin clearly and briskly presents instruction along with source code.
Analyzed and implemented in Java, the data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search trees including treaps, scapegoat trees, and red-black trees; integer searching structures including binary tries, x-fast tries, and y-fast tries; heaps, including implicit binary heaps and randomized meldable heaps; graphs, including adjacency matrix and adjacency list representations; and B-trees.
A modern treatment of an essential computer science topic, Open Data Structures is a measured balance between classical topics and state-of-the art structures that will serve the needs of all undergraduate students or self-directed learners.
About the Contributors
Pat Morin is Professor in the School of Computer Science at Carleton University as well as founder and managing editor of the open access Journal of Computational Geometry. He is the author of numerous conference papers and journal publications on the topics of computational geometry, algorithms, and data structures.