Sign up for AU Press news

View AU Press 2018 Fall Catalogue

University Press Week 2015 banner

การพนัน ภาษาอังกฤษ_ทีเด็ด ฟุตบอล วัน นี้ 3 คู่_สล็อต ฟรี เครดิต ถอน ได้

[book cover] Open Data Structures

Pat Morin

Order paperback

August 2013

9781927356388 (Paperback)
9781927356395 (PDF)


OPEL (Open Paths to Enriched Learning)




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 Authors

Pat Morin is an associate 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.



Download the eBook

Copyright: This work is licensed under a Creative Commons License (CC BY-NC-ND 2.5 CA). It may be reproduced for non-commercial purposes, provided that the original author is credited.


Download the entire book

Select a Chapter

DownloadFront Matter

DownloadTable of Contents


เกมส์ยิงปลาออนไลน์DownloadWhy This Book?

เกมส์ยิงปลาออนไลน์DownloadChapter 1.  Introduction

1.1 The Need for Efficiency

1.2 Interfaces

1.2.1 The Queue, Stack, and Deque Interfaces

1.2.2 The List Interface: Linear Sequences

1.2.3 The USet Interface: Unordered Sets

1.2.4 The SSet Interface: Sorted Sets

1.3 Mathematical Background

1.3.1 Exponentials and Logarithms

1.3.2 Factorials

1.3.3 Asymptotic Notation

1.3.4 Randomization and Probability

1.4 The Model of Computation

1.5 Correctness, Time Complexity, and Space Complexity

1.6 Code Samples

1.7 List of Data Structures

1.8 Discussion and Exercises

DownloadChapter 2.  Array-Based Lists

2.1 ArrayStack: Fast Stack Operations Using an Array

2.1.1 The Basics

2.1.2 Growing and Shrinking

2.1.3 Summary

2.2 FastArrayStack: An Optimized ArrayStack

2.3 ArrayQueue: An Array-Based Queue

2.3.1 Summary

2.4 ArrayDeque: Fast Deque Operations Using an Array

2.4.1 Summary

2.5 DualArrayDeque: Building a Deque from Two Stacks

2.5.1 Balancing

2.5.2 Summary

2.6 RootishArrayStack: A Space-Efficient Array Stack

2.6.1 Analysis of Growing and Shrinking

2.6.2 Space Usage

2.6.3 Summary

2.6.4 Computing Square Roots

2.7 Discussion and Exercises

DownloadChapter 3.  Linked Lists

3.1 SLList: A Singly-Linked List

3.1.1 Queue Operations

3.1.2 Summary

3.2 DLList: A Doubly-Linked List

3.2.1 Adding and Removing

3.2.2 Summary

3.3 SEList: A Space-Efficient Linked List

3.3.1 Space Requirements

3.3.2 Finding Elements

3.3.3 Adding an Element

3.3.4 Removing an Element

3.3.5 Amortized Analysis of Spreading and Gathering

3.3.6 Summary

3.4 Discussion and Exercises

DownloadChapter 4.  Skiplists

4.1 The Basic Structure

4.2 SkiplistSSet: An Efficient SSet

4.2.1 Summary

4.3 SkiplistList: An Efficient Random-Access List

4.3.1 Summary

4.4 Analysis of Skiplists

4.5 Discussion and Exercises

DownloadChapter 5.  Hash Tables

5.1 ChainedHashTable: Hashing with Chaining

5.1.1 Multiplicative Hashing

5.1.2 Summary

5.2 LinearHashTable: Linear Probing

5.2.1 Analysis of Linear Probing

5.2.2 Summary

5.2.3 Tabulation Hashing

5.3 Hash Codes

5.3.1 Hash Codes for Primitive Data Types

5.3.2 Hash Codes for Compound Objects

5.3.3 Hash Codes for Arrays and Strings

5.4 Discussion and Exercises

DownloadChapter 6.  Binary Trees

6.1 BinaryTree: A Basic Binary Tree

6.1.1 Recursive Algorithms

6.1.2 Traversing Binary Trees

6.2 BinarySearchTree: An Unbalanced Binary Search Tree

6.2.1 Searching

6.2.2 Addition

6.2.3 Removal

6.2.4 Summary

6.3 Discussion and Exercises

DownloadChapter 7.  Random Binary Search Trees

7.1 Random Binary Search Trees

7.1.1 Proof of Lemma 7.1

7.1.2 Summary

7.2 Treap: A Randomized Binary Search Tree

7.2.1 Summary

7.3 Discussion and Exercises

DownloadChapter 8.  Scapegoat Trees

8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding

8.1.1 Analysis of Correctness and Running-Time

8.1.2 Summary

8.2 Discussion and Exercises

DownloadChapter 9.  Red-Black Trees

9.1 2-4 Trees

9.1.1 Adding a Leaf

9.1.2 Removing a Leaf

9.2 RedBlackTree: A Simulated 2-4 Tree

9.2.1 Red-Black Trees and 2-4 Trees

9.2.2 Left-Leaning Red-Black Trees

9.2.3 Addition

9.2.4 Removal

9.3 Summary

9.4 Discussion and Exercises

DownloadChapter 10.  Heaps

10.1 BinaryHeap: An Implicit Binary Tree

10.1.1 Summary

10.2 MeldableHeap: A Randomized Meldable Heap

10.2.1 Analysis of merge(h1, h2)

10.2.2 Summary

10.3 Discussion and Exercises

DownloadChapter 11.  Sorting Algorithms

11.1 Comparison-Based Sorting

11.1.1 Merge-Sort

11.1.2 Quicksort

11.1.3 Heap-sort

11.1.4 A Lower-Bound for Comparison-Based Sorting

11.2 Counting Sort and Radix Sort

11.2.1 Counting Sort

11.2.2 Radix-Sort

11.3 Discussion and Exercises

เกมส์ยิงปลาออนไลน์DownloadChapter 12.  Graphs

12.1 AdjacencyMatrix: Representing a Graph by a Matrix

12.2 AdjacencyLists: A Graph as a Collection of Lists

12.3 Graph Traversal

12.3.1 Breadth-First Search

12.3.2 Depth-First Search

12.4 Discussion and Exercises

DownloadChapter 13.  Data Structures for Integers

13.1 BinaryTrie: A digital search tree

13.2 XFastTrie: Searching in Doubly-Logarithmic Time

13.3 YFastTrie: A Doubly-Logarithmic Time SSet

13.4 Discussion and Exercises

DownloadChapter 14.  External Memory Searching

14.1 The Block Store

14.2 B-Trees

14.2.1 Searching

14.2.2 Addition

14.2.3 Removal

14.2.4 Amortized Analysis of B-Trees

14.3 Discussion and Exercises