Overview

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.

Full Product Details

Author:   Pat Morin
Publisher:   AU Press
Imprint:   AU Press
Edition:   31st
Dimensions:   Width: 15.20cm , Height: 2.30cm , Length: 22.90cm
Weight:   0.540kg
ISBN:  

9781927356388

ISBN 10:   1927356385
Pages:   344
Publication Date:   01 June 2013
Audience:   College/higher education ,  Professional and scholarly ,  Tertiary & Higher Education ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

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  

Reviews

Author Information

Pat Morin is Professor in the School of ComputerScience at Carleton University as well as founder and managing editorof the open access Journal of Computational Geometry. He is the authorof numerous conference papers and journal publications on the topics ofcomputational geometry, algorithms, and data structures. 

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions