I am pleased to announce the following open content textbooks
Open Data Structures (in Java) Edition 0.1
Open Data Structures (in C++) Edition 0.1Beta
These books, and accompanying source code, are freely available at
http://opendatastructures.org/
About
Open Data Structures covers the implementation and analysis of data
structures for sequences (lists), queues, priority queues, unordered
dictionaries, and ordered dictionaries.
Data structures presented in the book include stacks, queues, deques,
and lists implemented as arrays and linked-list; space-efficient
implementations of lists; skip lists; hash tables and hash codes;
binary search trees including treaps, scapegoat trees, and red-black
trees; and heaps, including implicit binary heaps and randomized
meldable heaps.
The data structures in this book are all fast, practical, and have
provably good running times. All data structures are rigorously
analyzed and implemented in Java and C++. The Java implementations
implement the corresponding interfaces in the Java Collections
Framework.
The book and accompanying source code are free (libre and gratis) and
are released under a Creative Commons Attribution License. Users are
free to copy, distribute, use, and adapt the text and source code,
even commercially. The book's LaTeX sources, Java/C++ sources, and
build scripts are available through github.
Table of Contents
1 Introduction
1.1 Interfaces
1.2 Mathematical Background
1.3 The Model of Computation
1.4 Code Samples
1.5 List of Data Structures
1.6 References
2 Array-Based Lists
2.1 ArrayStack: Fast Stack Operations Using an Array
2.2 FastArrayStack: An Optimized ArrayStack
2.3 ArrayQueue: An Array-Based Queue
2.4 ArrayDeque: Fast Deque Operations Using an Array
2.5 DualArrayDeque: Building a Deque from Two Stacks
2.6 RootishArrayStack: A Space-Efficient Array Stack
2.7 Discussion and Exercises
3 Linked Lists
3.1 SLList: A Singly-Linked List
3.2 DLList: A Doubly-Linked List
3.3 SEList: A Space-Efficient Linked List
3.4 Discussion and Exercises
4 Skiplists
4.1 The Basic Structure
4.2 SkiplistSSet: An Efficient SSet Implementation
4.3 SkiplistList: An Efficient Random-Access List Implementation
4.4 Analysis of Skiplists
4.5 Discussion and Exercises
5 Hash Tables
5.1 ChainedHashTable: Hashing with Chaining
5.2 LinearHashTable: Linear Probing
5.3 Hash Codes
5.4 Discussion and Exercises
6 Binary Trees
6.1 BinaryTree: A Basic Binary Tree
6.2 BinarySearchTree: An Unbalanced Binary Search Tree
6.3 Discussion and Exercises
7 Random Binary Search Trees
7.1 Random Binary Search Trees
7.2 Treap: A Randomized Binary Search Tree
7.3 Discussion and Exercises
8 Scapegoat Trees
8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding
8.2 Discussion and Exercises
9 Red-Black Trees
9.1 2-4 Trees
9.2 RedBlackTree: A Simulated 2-4 Tree
9.3 Summary
9.4 Discussion and Exercises
10 Heaps
10.1 BinaryHeap: An Implicit Binary Tree
10.2 MeldableHeap: A Randomized Meldable Heap
10.3 Discussion and Exercises
11 Sorting Algorithms
11.1 Comparison-Based Sorting
11.2 Counting Sort and Radix Sort
11.3 Discussion and Exercises
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
