| |
| |
| Fundamentals | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Algorithms | |
| |
| |
| |
| A Sample Problem: Connectivity | |
| |
| |
| |
| Union-Find Algorithms | |
| |
| |
| |
| Perspective | |
| |
| |
| |
| Summary of Topics | |
| |
| |
| |
| Principles of Algorithm Analysis | |
| |
| |
| |
| Implementation and Empirical Analysis | |
| |
| |
| |
| Analysis of Algorithms | |
| |
| |
| |
| Growth of Functions | |
| |
| |
| |
| Big-Oh Notation | |
| |
| |
| |
| Basic Recurrences | |
| |
| |
| |
| Examples of Algorithm Analysis | |
| |
| |
| |
| Guarantees, Predictions, and Limitations | |
| |
| |
| Data Structures | |
| |
| |
| |
| Elementary Data Structures | |
| |
| |
| |
| Building Blocks | |
| |
| |
| |
| Arrays | |
| |
| |
| |
| Linked Lists | |
| |
| |
| |
| Elementary List Processing | |
| |
| |
| |
| Memory Allocation for Lists | |
| |
| |
| |
| Strings | |
| |
| |
| |
| Compound Data Structures | |
| |
| |
| |
| Abstract Data Types | |
| |
| |
| |
| Collections of Items | |
| |
| |
| |
| Pushdown Stack ADT | |
| |
| |
| |
| Examples of Stack ADT Clients | |
| |
| |
| |
| Stack ADT Implementations | |
| |
| |
| |
| Generic Implementations | |
| |
| |
| |
| Creation of a New ADT | |
| |
| |
| |
| FIFO Queues and Generalized Queues | |
| |
| |
| |
| Duplicate and Index Items | |
| |
| |
| |
| First-Class ADTs | |
| |
| |
| |
| Application-Based ADT Example | |
| |
| |
| |
| Perspective | |
| |
| |
| |
| Recursion and Trees | |
| |
| |
| |
| Recursive Algorithms | |
| |
| |
| |
| Divide and Conquer | |
| |
| |
| |
| Dynamic Programming | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Mathematical Properties of Trees | |
| |
| |
| |
| Tree Traversal | |
| |
| |
| |
| Recursive Binary-Tree Algorithms | |
| |
| |
| |
| Graph Traversal | |
| |
| |
| |
| Perspective | |
| |
| |
| Sorting | |
| |
| |
| |
| Elementary Sorting Methods | |
| |
| |
| |
| Rules of the Game | |
| |
| |
| |
| Generic Sort Implementations | |
| |
| |
| |
| Selection Sort | |
| |
| |
| |
| Insertion Sort | |
| |
| |
| |
| Bubble Sort | |
| |
| |
| |
| Performance Characteristics of Elementary Sorts | |
| |
| |
| |
| Algorithm Visualization | |
| |
| |
| |
| Shellsort | |
| |
| |
| |
| Sorting Linked Lists | |
| |
| |
| |
| Key-Indexed Counting | |
| |
| |
| |
| Quicksort | |
| |
| |
| |
| The Basic Algorithm | |
| |
| |
| |
| Performance Characteristics of Quicksort | |
| |
| |
| |
| Stack Size | |
| |
| |
| |
| Small Subfiles | |
| |
| |
| |
| Median-of-Three Partitioning | |
| |
| |
| |
| Duplicate Keys | |
| |
| |
| |
| Strings and Vectors | |
| |
| |
| |
| Selection | |
| |
| |
| |
| Merging and Mergesort | |
| |
| |
| |
| Two-Way Merging | |
| |
| |
| |
| Abstract In-Place Merge | |
| |
| |
| |
| Top-Down Mergesort | |
| |
| |
| |
| Improvements to the Basic Algorithm | |
| |
| |
| |
| Bottom-Up Mergesort | |
| |
| |
| |
| Performance Characteristics of Mergesort | |
| |
| |
| |
| Linked-List Implementations of Mergesort | |
| |
| |
| |
| Recursion Revisited | |
| |
| |
| |
| Priority Queues and Heapsort | |
| |
| |
| |
| Elementary Implementations | |
| |
| |
| |
| Heap Data Structure | |
| |
| |
| |
| Algorithms on Heaps | |
| |
| |
| |
| Heapsort | |
| |
| |
| |
| Priority-Queue ADT | |
| |
| |
| |
| Priority Queues for Client Arrays | |
| |
| |
| |
| Binomial Queues | |
| |
| |
| |
| Radix Sorting | |
| |
| |
| |
| Bits, Bytes, and Words | |
| |
| |
| |
| Binary Quicksort | |
| |
| |
| |
| MSD Radix Sort | |
| |
| |
| |
| Three-Way Radix Quicksort | |
| |
| |
| |
| LSD Radix Sort | |
| |
| |
| |
| Performance Characteristics of Radix Sorts | |
| |
| |
| |
| Sublinear-Time Sorts | |
| |
| |
| |
| Special-Purpose Sorting Methods | |
| |
| |
| |
| Batcher's Odd-Even Mergesort | |
| |
| |
| |
| Sorting Networks | |
| |
| |
| |
| Sorting In Place | |
| |
| |
| |
| External Sorting | |
| |
| |
| |
| Sort-Merge Implementations | |
| |
| |
| |
| Parallel Sort-Merge | |
| |
| |
| Searching | |
| |
| |
| |
| Symbol Tables and BSTs | |
| |
| |
| |
| Symbol-Table Abstract Data Type | |
| |
| |
| |
| Key-Indexed Search | |
| |
| |
| |
| Sequential Search | |
| |
| |
| |
| Binary Search | |
| |
| |
| |
| Index Implementations with Symbol Tables | |
| |
| |
| |
| Binary Search Trees | |
| |
| |
| |
| Performance Characteristics of BSTs | |
| |
| |
| |
| Insertion at the Root in BSTs | |
| |
| |
| |
| BST Implementations of Other ADT Operations | |
| |
| |
| |
| Balanced Trees | |
| |
| |
| |
| Randomized BSTs | |
| |
| |
| |
| Splay BSTs | |
| |
| |
| |
| Top-Down 2-3-4 Trees | |
| |
| |
| |
| Red-Black Trees | |
| |
| |
| |
| Skip Lists | |
| |
| |
| |
| Performance Characteristics | |
| |
| |
| |
| Hashing | |
| |
| |
| |
| Hash Functions | |
| |
| |
| |
| Separate Chaining | |
| |
| |
| |
| Linear Probing | |
| |
| |
| |
| Double Hashing | |
| |
| |
| |
| Dynamic Hash Tables | |
| |
| |
| |
| Perspective | |
| |
| |
| |
| Radix Search | |
| |
| |
| |
| Digital Search Trees | |
| |
| |
| |
| Tries | |
| |
| |
| |
| Patricia Tries | |
| |
| |
| |
| Multiway Tries and TSTs | |
| |
| |
| |
| Text-String-Index Applications | |
| |
| |
| |
| External Searching | |
| |
| |
| |
| Rules of the Game | |
| |
| |
| |
| Indexed Sequential Access | |
| |
| |
| |
| B Trees | |
| |
| |
| |
| Extendible Hashing | |
| |
| |
| |
| Perspective | |
| |
| |
| Appendix | |
| |
| |
| Index | |