CHAPTER 1 BASIC CONCEPTS
1.1 Overview: System Life Cycle
1.2 Pointers and Dynamic Memory Allocation
1.2.1 Pointers
1.2.2 Dynamic Memory Allocation
1.2.3 Pointers Can Be Dangerous
1.3 Algorithm Specification
1.3.1 Introduction
1.3.2 Recursive Algorithms
1.4 Data Abstraction
1.5 Performance Analysis
1.5.1 Space Complexity
1.5.2 Time Complexity
1.5.3 Asymptotic Notation
1.5.4 Practical Complexities
1.6 Performance Measurement
1.6.1 Clocking
1.6.2 Generating Test Data
1.7 Referenes And Selected Readings

CHAPTER 2 ARRAYS AND STRUCTURES
2.1 Arrays
2.1.1 The Abstract Data Type
2.1.2 Arrays in C
2.2 Dynamically Allocated Arrays
2.2.1 One-dimensional Arrays
2.2.2 Two-dimensional Arrays
2.3 Structures and Unions
2.3.1 Strctures
2.3.2 Unions
2.3.3 Internal Representation of Structures
2.3.4 Self-referential Structures
2.4 Polynomials
2.4.1 The Abstract Data Type
2.4.2 Polynomial Representation
2.4.3 Polynomial Addition
2.5 Sparse Matrices
2.5.1 The Abstract Data Type
2.5.2 Sparse Matrix Representation
2.5.3 Transposing a Matrix
2.5.4 Matrix Multiplication
2.6 Representation of Multidimensional Arrays
2.7 Strings
2.7.1 The Abstract Data Type
2.7.2 Strings in C
2.7.3 Pattern Matching
2.8 References and Selected Readings
2.9 Additional Exercises

CHAPTER 3 STACKS AND QUEUES
3.1 Stacks
3.2 Stacks Using Dynamic Arrays
3.3 Queues
3.4 Circular Queues Using Dynamic Arrays
3.5 A Mazing Problem
3.6 Evaluation of Expressions
3.6.1 Expressions
3.6.2 Evaluating Postfix Expressions
3.7 Multiple Stacks and Queues

3.7 Additional Exercises

CHAPTER 4 LINKED LISTS
4.1 Singly Linked Lists and Chains
4.2 Representing Chains in C
4.3 Linked Stacks and Queues
4.4 Polynomials
4.4.1 Polynomial Representation
4.4.2 Adding Polynomials
4.4.3 Erasing Polynomials
4.4.4 Circular List Representation of Polynomials
4.4.5 Summary
4.5 Additional List Operations
4.5.1 Operations for Chains
4.5.2 Operations for Circularly Linked Lists
4.6 Equivalence Classes
4.7 Sparse Matrices
4.7.1 Sparse Matrix Representation
4.7.2 Sparse Matrix Input
4.7.3 Sparse Matrix Output
4.7.4 Erasing a Sparse Matrix
4.8 Doubly Linked Lists

CHAPTER 5 TREES
5.1 Introduction
5.1.1 Terminology
5.1.2 Representation of Trees
5.2 Binary Trees
5.2.1 The Abstract Data Type
5.2.2 Properties of Binary Trees
5.2.3 Binary Tree Representations
5.3 Binary Tree Traversals

5.3.1 Inorder Traversal

5.3.2 Preorder Traversal
5.3.3Postorder Traversal
5.3.4 Iterative Inorder Traversal
5.3.5 Level-Order Traversal
5.3.6 Traversal Without a Stack
5.4 Additional Binary Tree Operations
5.4.1 Copying Binary Trees
5.4.2 Testing Equality
5.4.3 The Satisfiability Problem
5.5 Threaded Binary Trees
5.5.1 Threads
5.5.2 Inorder Traversal of a Threaded Binary Tree
5.5.3 Inserting a Node into a Threaded Binary Tree
5.6 Heaps
5.6.1 Priority Ques
5.6.2 Definition of a Max Heap
5.6.3 Insertion into a Max Heap
5.6.4 Deletion from a Max Heap
5.7 Binary Search Trees
5.7.1 Definition
5.7.2 Searching a Binary Search Tree
5.7.3 Insertion into a Binary Search Tree
5.7.4 Deletion from a Binary Search Tree
5.7.5 Joining and Splitting Binary Search Trees
5.7.6 Height of a Binary Search Tree
5.8 Selection Trees

5.8.1 Introduction


5.8.2 Winner Trees
5.8.3 Loser Trees
5.9 Forests

5.9.1 Transforming a Forest into a Binary Tree
5.9.2 Forest Traversals
5.10 Representation of Disjoint Sets

5.10.1 Introduction

5.10.2 Union and find Operations
5.10.3 Application to Equivalence Classes
5.11 Counting Binary Trees
5.11.1 Distinct Binary Trees
5.11.2 Stack Permutations
5.11.3 Matrix Multiplication
5.11.4 Number of Distinct Binary Trees
5.12 References and Selected Readings

CHAPTER 6 GRAPHS
6.1 The Graph Abstract Data Type
6.1.1 Introduction
6.1.2 Definitions
6.1.3 Graph Representations
6.2 Elementary Graph Operations
6.2.1 Depth First Search
6.2.2 Breadth First Search
6.2.3 Connected Components
6.2.4 Spanning Trees
6.2.5 Biconnected Components
6.3 Minimum Cost Spanning Trees
6.3.1 Kruskal’s Algorithm
6.3.2 Prim’s Algorithm
6.3.3 Sollin’s Algorithm
6.4 Shortest Paths and Transitive Closure
6.4.1 Single Source/All Destination: Nonnegative Edge Costs
6.4.2 Single Source/all Destination: General Weights
6.4.3 All Pairs Shortest Paths
6.4.4 Transitive Closure
6.5 Activity Networks
6.5.1 Activity-on-Vertex (AOV) Networks
6.5.2 Activity-on-Edge (AOE) Networks
6.6 References and Selected Readings
6.7 Additional Exercises

CHAPTER 7 SORTING
7.1 Motivation
7.2 Insertion Sort
7.3 Quick Sort
7.4 How Fast Can We Sort?
7.5 Merge Sort
7.5.1 Merging
7.5.2 Interative Merge Sort
7.5.3 Recursive Merge Sort
7.6 Heap Sort
7.7 Sorting on Several Keys
7.8 List and Table Sorts
7.9 Summary of Internal Sorting
7.10 External Sorting
7.10.1 Introduction
7.10.2 k-way Merging
7.10.3 Buffer Handling for Parallel Operation
7.10.4 Run Generation
7.10.5 Optimal Merging of Runs
7.11 References and Selected Readings

CHAPTER 8 HASHING
8.1 Introduction

8.2 Static Hashing
8.2.1 Hash Tables
8.2.2 Hash Functions
8.2.3 Overflow Handling
8.2.4 Theoretical Evaluation of Overflow Techniques
8.3 Dynamic Hashing
8.3.1 Motivation for Dynamic Hashing
8.3.2 Dynamic Hashing using Directories
8.3.3 Directoryless Dynamic Hashing
8.4 Bloom Filters
8.4.1 An Application--Differential Files
8.4.2 Bloom Filter Design
8.5 References and selected Readings

CHAPTER 9 PRIORITY QUEUES
9.1 Single- and Double-Ended Priority Queues
9.2 Leftist Trees
9.2.1 Height-Biased Leftist Trees
9.2.2 Weight-Biased Leftist Trees
9.3 Binomial Heaps
9.3.1 Cost Amortization
9.3.2 Definition of Binomial Heaps
9.3.3 Insertion into a Binomial Heap
9.3.4 Melding Two Binomial Heaps
9.3.5 Deletion of Min Element
9.3.6 Analysis
9.4 Fibonacci Heaps
9.4.1 Definition
9.4.2 Deletion from an f-heap
9.4.3 Decrease Key
9.4.4 Cascading Cut
9.4.5 Analysis
9.4.6 Application to The Shortest Paths Problem
9.5 Pairing Heaps
9.5.1 Definition
9.5.2 Meld and Insert
9.5.3 Decrease Key
9.5.4 Delete Min
9.5.5 Arbitrary Delete
9.5.6 Implementation Considerations
9.5.7 Complexity
9.6 Symmetric Min-Max Heaps
9.6.1 Definition and Properties
9.6.2 SMMH Representation
9.6.3 Inserting into an SMMH
9.6.4 Deleting from an SMMH
9.7 Interval Heaps
9.7.1 Definition and Properties
9.7.2 Inserting into an Interval Heap
9.7.3 Deleting the Min Element
9.7.4 Initializing an Interval Heap
9.7.5 Complexity of Interval Heap Operations
9.7.6 The Complementary Range Search Problem
9.8 References and Selected Readings

CHAPTER 10 EFFICIENT BINARY SEARCH TREES
10.1 Optimal Binary Search Trees
10.2 AVL Trees
10.3 Red-Black Trees
10.3.1 Definition
10.3.2 Representation of a Red-Black Tree
10.3.3 Searching a Red-Black Tree
10.3.4 Inserting to a Red-Black Tree
10.3.5 Deletion from a Red-Black Tree
10.3.6 Joining Red-Black Trees
10.3.7 Splitting a Red-Black Tree
10.4 Splay Trees
10.4.1 Bottom-Up Splay Trees
10.4.2 Top-Down Splay Trees
10.5 References and Selected Readings

CHAPTER 11 MULTIWAY SEARCH TREES
11.1 m-way Search Trees
11.1.1 Definition and Properties
11.1.2 Searching an m-way Search Tree
11.2 B-Trees
11.2.1 Definition and Properties
11.2.2 Number of Elements in a B-Tree
11.2.3 Insertion into a B-tree
11.2.4 Deletion from a B-tree
11.3 B-Trees
11.3.1 Definition
11.3.2 Searching a B____________Tree
11.3.3 Insertion into a B____________Tree
11.3.4 Deletion from a B____________Tree
11.4 References and Selected Readings

CHAPTER 12 DIGITAL SEARCH STRUCTURES
12.1 Digital Search Trees

12.1.1 Definition

12.1.2 Search, Insert and Delete
12.2 Binary Tries and Patricia
12.2.1 Binary Tries
12.2.2 Compressed Binary Tries
12.2.3 Patricia
12.3 Multiway Tries
12.3.1 Definition
12.3.2 Searching a Trie
12.3.3 Sampling Strategies
12.3.4 Insertion into a Trie
12.3.5 Deletion from a Trie
12.3.6 Keys with Different Length
12.3.7 Height of a Trie
12.3.8 Space Required and Alternative Node Structures
12.3.9 Prefix Search and Applications
12.3.10 Compressed Tries
12.3.11 Compressed Tries with Skip Fields
12.3.12 Compressed Tries with Labeled Edges
12.3.13 Space Required by a Compressed Trie
12.4 Suffix Trees
12.4.1 Have you Seen this String?
12.4.2 The Suffix Tree Data Structure
12.4.3 Let’s Find That Substring (Searching a Suffix Tree)
12.4.4 Other Nifty Things You Can Do with a Suffix Tree
12.5 Tries and Internet Packet Forwarding
12.5.1 IP Routing
12.5.2 I-Bit Tries
12.5.3 Fixed-Stride Tries
12.5.4 Variable-Stride Tries
12.6 References and Selected Readings