| |
| |
| |
Introduction | |
| |
| |
What's the Book About? | |
| |
| |
Mathematics Review | |
| |
| |
Exponents | |
| |
| |
Logarithms | |
| |
| |
Series | |
| |
| |
Modular Arithmetic | |
| |
| |
The P word | |
| |
| |
A Brief Introduction to Recursion | |
| |
| |
| |
Algorithm Analysis | |
| |
| |
Mathematical Background | |
| |
| |
Model | |
| |
| |
What to Analyze | |
| |
| |
Running Time Calculations | |
| |
| |
A Simple Example | |
| |
| |
General Rules | |
| |
| |
Solutions for the Maximum Subsequence Sum Problem | |
| |
| |
Logarithms in the Running Time | |
| |
| |
Checking Your Analysis | |
| |
| |
A Grain of Salt | |
| |
| |
| |
Lists, Stacks, and Queues | |
| |
| |
Abstract Data Types (ADTs) | |
| |
| |
The List ADT | |
| |
| |
Simple Array Implementation of Lists | |
| |
| |
Linked Lists | |
| |
| |
Programming Details | |
| |
| |
Common Errors | |
| |
| |
Doubly Linked Lists | |
| |
| |
Circularly Linked Lists | |
| |
| |
Examples | |
| |
| |
Cursor Implementation of Linked Lists | |
| |
| |
The Stack ADT | |
| |
| |
Stack Model | |
| |
| |
Implementation of Stacks | |
| |
| |
Applications | |
| |
| |
The Queue ADT | |
| |
| |
Queue Model | |
| |
| |
Array Implementation of Queues | |
| |
| |
Applications of Queues | |
| |
| |
| |
Trees | |
| |
| |
Preliminaries | |
| |
| |
Implementation of Trees | |
| |
| |
Tree Traversals with an Application | |
| |
| |
Binary Trees | |
| |
| |
Implementation | |
| |
| |
Expression Trees | |
| |
| |
The Search Tree ADT—Binary Search Trees | |
| |
| |
MakeEmpty | |
| |
| |
Find | |
| |
| |
FindMin and FindMax | |
| |
| |
Insert | |
| |
| |
Delete | |
| |
| |
Average-Case Analysis | |
| |
| |
AVL Trees | |
| |
| |
Single Rotation | |
| |
| |
Double Rotation | |
| |
| |
Splay Trees | |
| |
| |
A Simple Idea (That Does Not Work) | |
| |
| |
Splaying | |
| |
| |
Tree Traversals (Revisited) | |
| |
| |
B-Trees | |
| |
| |
| |
Hashing | |
| |
| |
General Idea | |
| |
| |
Hash Function | |
| |
| |
Separate Chaining | |
| |
| |
Open Addressing | |
| |
| |
Linear Probing | |
| |
| |
Quadratic Probing | |
| |
| |
Double Hashing | |
| |
| |
Rehashing | |
| |
| |
Extendible Hashing | |
| |
| |
| |
Priority Queues (Heaps) | |
| |
| |
Model | |
| |
| |
Simple Implementations | |
| |
| |
Binary Heaps | |
| |
| |
Structure Property | |
| |
| |
Heap Order Property | |
| |
| |
Basic Heap Operations | |
| |
| |
Other Heap Operations | |
| |
| |
Applications of Priority Queues | |
| |
| |
The Selection Problem | |
| |
| |
Event Simulation | |
| |
| |
d-Heaps | |
| |
| |
Leftist Heaps | |
| |
| |
Leftist Heap Property | |
| |
| |
Leftist Heap Operations | |
| |
| |
Skew Heaps | |
| |
| |
Binomial Queues | |
| |
| |
Binomial Queue Structure | |
| |
| |
Binomial Queue Operations | |
| |
| |
Implementations of Binomial Queues | |
| |
| |
| |
Sorting | |
| |
| |
Preliminaries | |
| |
| |
Insertion Sort | |
| |
| |
The Algorithm | |
| |
| |
Analysis of Insertion Sort | |
| |
| |
A Lower Bound for Simple Sorting Algorithms | |
| |
| |
Shellsort | |
| |
| |
Analysis of Insertion Sort | |
| |
| |
Heapsort | |
| |
| |
Analysis of Heapsort | |
| |
| |
Mergesort | |
| |
| |
Analysis of Mergesort | |
| |
| |
Quicksort | |
| |
| |
Picking the Pivot | |
| |
| |
Partitioning Strategy | |
| |
| |
Small Arrays | |
| |
| |
Actual Quicksort Routines | |
| |
| |
Analysis of Quicksort | |
| |
| |
A Linear-Expected-Time Algorithm for Selection | |
| |
| |
Sorting Large Structures | |
| |
| |
A General Lower Bound for Sorting | |
| |
| |
Decision Trees | |
| |
| |
Bucket Sort | |
| |
| |
External Sorting | |
| |
| |
Why We Need New Algorithms | |
| |
| |
Model for External Sorting | |
| |
| |
The Simple Algorithm | |
| |
| |
Multiway Merge | |
| |
| |
Polyphase Merge | |
| |
| |
Replacement Selection | |
| |
| |
| |
The Disjoint Set ADT | |
| |
| |
Equivalence Relations | |
| |
| |
The Dynamic Equivalence Problem | |
| |
| |
Basic Data Structure | |
| |
| |
Smart Union Algorithms | |
| |
| |
Path Compression | |
| |
| |
Worst Case for Union-by-Rank and Path Compression | |
| |
| |
Analysis of the Union/Find Algorithm | |
| |
| |
An Application | |
| |
| |
| |
Graph Algorithms | |
| |
| |
Definitions | |
| |
| |
Representation of Graphs | |
| |
| |
Topological Sort | |
| |
| |
Shortest-Path Algorithms | |
| |
| |
Unweighted Shortest Paths | |
| |
| |
Dijkstra's Algorithm | |
| |
| |
Graphs with Negative Edge Costs | |
| |
| |
Acyclic Graphs | |
| |
| |
All-Pairs Shortest Path | |
| |
| |
Network Flow Problems | |
| |
| |
A Simple Maximum-Flow Algorithm | |
| |
| |
Minimum Spanning Tree | |
| |
| |
Prim's Algorithm | |
| |
| |
Kruskal's Algorithm | |
| |
| |
Applications of Depth-First Search | |
| |
| |
Undirected Graphs | |
| |
| |
Biconnectivity | |
| |
| |
Euler Circuits | |
| |
| |
Directed Graphs | |
| |
| |
Finding Strong Components | |
| |
| |
Introduction to the NP-Completeness | |
| |
| |
Easy vs. Hard | |
| |
| |
The Class NP | |
| |
| |
NP-Complete Problems | |
| |
| |
| |
Algorithm Design Techniques | |
| |
| |
Greedy Algorithms | |
| |
| |
A Simple Scheduling Problem | |
| |
| |
Huffman Codes | |
| |
| |
Approximate Bin Packing | |
| |
| |
Divide and Conquer | |
| |
| |
Running Time of Divide and Conquer Algorithms | |
| |
| |
Closest-Points Problem | |
| |
| |
The Selection Problem | |
| |
| |
Theoretical Improvements for Arithmetic Problems | |
| |
| |
Dynamic Programming | |
| |
| |
Using a Table Instead of Recursion | |
| |
| |
Ordering Matrix Multiplications | |
| |
| |
Optimal Binary Search Tree | |
| |
| |
All-Pairs Shortest Path | |
| |
| |
Randomized Algorithms | |
| |
| |
Random Number Generators | |
| |
| |
Skip Lists | |
| |
| |
Primality Testing | |
| |
| |
Backtracking Algorithms | |
| |
| |
The Turnpike Reconstruction Problem | |
| |
| |
Games | |
| |
| |
| |
Amortized Analysis | |
| |
| |
An Unrelated Puzzle | |
| |
| |
Binomial Queues | |
| |
| |
Skew Heaps | |
| |
| |
Fibonacci Heaps | |
| |
| |
Cutting Nodes in Leftist Heaps | |
| |
| |
Lazy Merging for Binomial Queues | |
| |
| |
The Fibonacci Heap Operations | |
| |
| |
Proof of the Time Bound | |
| |
| |
Splay Trees | |
| |
| |
| |
Advanced Data Structures and Implementation | |
| |
| |
Top-Down Splay Trees | |
| |
| |
Red Black Trees | |
| |
| |
Bottom-Up Insertion | |
| |
| |
Top-Down Red Black Trees | |
| |
| |
Top-Down Deletion | |
| |
| |
Deterministic Skip Lists | |
| |
| |
AA-Trees | |
| |
| |
Treaps | |
| |
| |
k-d Trees | |
| |
| |
Pairing Heaps | |
| |
| |
Index 0201498405T04062001<$$$> | |