Open Data Structures: An Introduction

Paperback | June 1, 2013

byPat Morin

not yet rated|write a review

Offered as an introduction to the field of data structures andalgorithms, Open Data Structures covers the implementation and analysisof data structures for sequences (lists), queues, priority queues,unordered dictionaries, ordered dictionaries, and graphs. Focusing on amathematically rigorous approach that is fast, practical, andefficient, Morin clearly and briskly presents instruction along withsource 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, Open DataStructures is a measured balance between classical topics andstate-of-the art structures that will serve the needs of allundergraduate students or self-directed learners.

 

Pricing and Purchase Info

$29.95

Ships within 1-3 weeks
Ships free on orders over $25

From the Publisher

Offered as an introduction to the field of data structures andalgorithms, Open Data Structures covers the implementation and analysisof data structures for sequences (lists), queues, priority queues,unordered dictionaries, ordered dictionaries, and graphs. Focusing on amathematically rigorous approach that is fast, practical, andeffici...

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. 
Format:PaperbackDimensions:344 pages, 9 × 6 × 0.83 inPublished:June 1, 2013Publisher:Athabasca University PressLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:1927356385

ISBN - 13:9781927356388

Look for similar items by category:

Customer Reviews of Open Data Structures: An Introduction

Reviews

Extra Content

Table of Contents

Acknowledgments- xi

Why This Book?- xiii

1. Introduction- 1

           1.1 The Need for Efficiency- 2

           1.2 Interfaces- 4

           1.3 Mathematical Background- 9

           1.4 The Model of Computation- 18

           1.5 Correctness, Time Complexity, and Space Complexity- 19

           1.6 Code Samples- 22

           1.7 List of Data Structures- 22

           1.8 Discussion and Exercises- 26

2. Array-Based Lists- 29

           2.1 ArrayStack: Fast Stack Operations Using an Array- 30

2.2 FastArrayStack: An Optimized ArrayStack- 35

2.3 ArrayQueue: An Array-Based Queue- 36

2.4 ArrayDeque: Fast Deque Operations Using an Array- 40

2.5 DualArrayDeque: Building a Deque from Two Stacks- 43

2.6 RootishArrayStack: A Space-Efficient Array Stack- 49

2.7 Discussion and Exercises- 59

3. Linked Lists- 63

           3.1 SLList: A Singly-Linked List- 63

           3.2 DLList: A Doubly-Linked List- 67

           3.3 SEList: A Space-Efficient Linked List- 71

           3.4 Discussion and Exercises- 82

4. Skiplists- 87

           4.1 The Basic Structure- 87

           4.2 SkiplistSSet: An Efficient Sset- 90

           4.3 SkiplistList: An Efficient Random-Access List- 93

           4.4 Analysis of Skiplists- 98

           4.5 Discussion and Exercises- 102

5. Hash Tables- 107

           5.1 ChainedHashTable: Hashing with Chaining- 107

           5.2 LinearHashTable: Linear Probing- 114

           5.3 Hash Codes- 122

           5.4 Discussion and Exercises- 128

6. Binary Trees- 133

           6.1 BinaryTree: A Basic Binary Tree- 135

           6.2 BinarySearchTree: An Unbalanced Binary Search Tree- 140

           6.3 Discussion and Exercises- 147

7. Random Binary Search Trees- 153

           7.1 Random Binary Search Trees- 153

           7.2 Treap: A Randomized Binary Search Tree- 159

           7.3 Discussion and Exercises- 168

8. Scapegoat Trees- 173

           8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding-173

           8.2 Discussion and Exercises- 181

9. Red-Black Trees- 185

           9.1 2-4 Trees- 186

           9.2 RedBlackTree: A Simulated 2-4 Tree- 190

           9.3 Summary- 205

           9.4 Discussion and Exercises- 206

10. Heaps- 211

           10.1 BinaryHeap: An Implicit Binary Tree- 211

           10.2 MeldableHeap: A Randomized Meldable Heap- 217

           10.3 Discussion and Exercises- 222

11. Sorting Algorithms- 225

           11.1 Comparison-Based Sorting- 226

           11.2 Counting Sort and Radix Sort- 238

           11.3 Discussion and Exercises- 243

12. Graphs- 247

           12.1 AdjacencyMatrix: Representing a Graph by a Matrix- 249

           12.2 AdjacencyLists: A Graph as a Collection of Lists- 252

           12.3 Graph Traversal- 256

           12.4 Discussion and Exercises- 261

13. Data Structures for Integers- 265

           13.1 BinaryTrie: A digital search tree- 266

           13.2 XFastTrie: Searching in Doubly-Logarithmic Time- 272

           13.3 YFastTrie: A Doubly-Logarithmic Time SSet- 275

           13.4 Discussion and Exercises- 280

14. External Memory Searching- 283

           14.1 The Block Store- 285

           14.2 B-Trees- 285

           14.3 Discussion and Exercises- 304

Bibliography- 309

Index- 317