# Open Data Structures: An Introduction

Pat Morin, Carleton University

Copyright Year: 2013

ISBN 13: 9781927356388

Publisher: Athabasca University Press

Language: English

## Formats Available

## Conditions of Use

Attribution-NonCommercial-NoDerivs

CC BY-NC-ND

## Reviews

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... read more

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.

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

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.

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

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

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

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.

The contents look great!

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.

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.

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.

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). read more

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

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

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

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.

The book's definitions and notation are consistent throughout.

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.

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

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

The text contains few grammatical errors.

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

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

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

- 1 Introduction
- 2 Array-Based Lists
- 3 Linked Lists
- 4 Skiplists
- 5 Hash Tables
- 6 Binary Trees
- 7 Random Binary Search Trees
- 8 Scapegoat Trees
- 9 Red-Black Trees
- 10 Heaps
- 11 Sorting Algorithms
- 12 Graphs
- 13 Data Structures for Integers
- 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

### Author

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