Open Data Structures: An Introduction (Open Paths to Enriched Learning) by Morin, Pat (2013) Paperback

by Pat Morin

Offered as an introduction to the field of data structures andalgorithms, "Open Data Structures" covers the implementation andanalysis of data structures for sequences (lists), queues, priorityqueues, unordered dictionaries, ordered dictionaries, and graphs.Focusing on a mathematically rigorous approach that is fast, practical, and efficient, Morin clearly and briskly presents instruction alongwith source code. Analyzed and implemented in Java, the data structures presented inthe book include stacks, queues, deques, and lists implemented asarrays and linked-lists; space-efficient implementations of lists; skiplists; hash tables and hash codes; binary search trees includingtreaps, scapegoat trees, and red-black trees; integer searchingstructures including binary tries, x-fast tries, and y-fast tries;heaps, including implicit binary heaps and randomized meldable heaps;and graphs, including adjacency matrix and adjacency listrepresentations; and B-trees. A modern treatment of an essential computer science topic, "OpenData Structures" is a measured balance between classical topics andstate-of-the art structures that will serve the needs of allundergraduate students or self-directed learners.Pat Morin is an associate professor in the School ofComputer Science at Carleton University as well as founder and managingeditor of the open access "Journal of Computational Geometry."He is the author of numerous conference papers and journal publicationson the topics of computational geometry, algorithms, and datastructures.

Genres: Computer Science, Programming, Nonfiction, Technology

Paperback

First published January 1, 2013

Reviews

[Damien · Rating 4 out of 5]

This is a nice and rigorous introduction to the topic of data structures and algorithms. The book is well-structured (no pun intended); the order of the chapters makes sense, some of the later chapters build on some of the earlier chapters. There is a common thread throughout and although the writing is minimal and to-the-point, it still feels like a journey through data structures.

If you have mainly written programs without giving much thought to efficiency and were mostly concerned with getting the desired result, this textbook is going to be an appropriate next step. Even if you don’t grasp every theorem and proof—I didn’t—, you will certainly gain the crucial reflex of thinking about the runtime complexity and the space efficiency of your algorithms.

Personally, my favourite takeaway from Open Data Structures is the ubiquity of randomness. If you, like myself, are fascinated by randomness, I promise you’re going to enjoy the various uses Morin presents of the concept. In many situations, the optimal implementation of a data structure requires and is built on randomness—fascinating!

Other qualities: Morin offers source codes and often adds welcomed visualizations of some methods (via figures). That being said, I highly encourage you to look online for (visual) simulations of the data structure/algorithm at hand—doing this has contributed to improving my understanding of the text.

On a final note, although there is a chapter on the mathematical prerequisites, some basic knowledge of probability (e.g., indicator random variable) may allow for smoother reading.

[Riyan · Rating 4 out of 5]

Used it for my class Comp2402. Decent book and simple enough most of the time. Some of the data structures were more esoteric, eg. Scapegoat trees, skiplist, dual array deques but they served as good learning tools.

[Amal · Rating 5 out of 5]

♥ Book 19 of 2021

★ Final Rating: 5 Star

[Christian · Rating 5 out of 5]

I loved it. This is a super high quality open source and free book on data structures that teaches the material well. It is concise, rigourous, and well written.

Update: In the many years since I've gone through it in undergrad, it is still my favourite data structures reference.