| |
| |
| |
Introduction | |
| |
| |
What's the Book About? | |
| |
| |
Mathematics Review | |
| |
| |
Exponents | |
| |
| |
Logarithms | |
| |
| |
Series | |
| |
| |
Modular Arithmetic | |
| |
| |
The P Word | |
| |
| |
A Brief Introduction to Recursion | |
| |
| |
C++ Classes | |
| |
| |
Basic class Syntax | |
| |
| |
Extra Constructor Syntax and Accessors | |
| |
| |
Separation of Interface and Implementation | |
| |
| |
Vector and string | |
| |
| |
C++ Details | |
| |
| |
Pointers | |
| |
| |
Parameter Passing | |
| |
| |
Return Passing | |
| |
| |
Reference Variables | |
| |
| |
The Big Three: Destructor, Copy Constructor, operator= | |
| |
| |
The World of C | |
| |
| |
Templates | |
| |
| |
Function Templates | |
| |
| |
Class Templates | |
| |
| |
Object, Comparable, and an Example | |
| |
| |
Using Matrices | |
| |
| |
The Data Members, Constructor, and Basic Accessors | |
| |
| |
Operator | |
| |
| |
Destructor, Copy Assignment, Copy Constructor | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
Lists, Stacks, and Queues | |
| |
| |
Abstract Data Types (ADTs) | |
| |
| |
The List ADT | |
| |
| |
Simple Array Implementation of Lists | |
| |
| |
Linked Lists | |
| |
| |
Programming Details | |
| |
| |
Memory Reclamation and the Big Three | |
| |
| |
Doubly Linked Lists | |
| |
| |
Circular 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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
| |
Trees | |
| |
| |
Preliminaries | |
| |
| |
Implementation of Trees | |
| |
| |
Tree Traversals with an Application | |
| |
| |
Binary Trees | |
| |
| |
Implementation | |
| |
| |
An Example: Expression Trees | |
| |
| |
The Search Tree ADT-Binary Search Trees | |
| |
| |
Find | |
| |
| |
FindMin and findMax | |
| |
| |
Insert | |
| |
| |
Remove | |
| |
| |
Destructor and Copy Assignment Operator | |
| |
| |
Average-Case Analysis | |
| |
| |
AVL Trees | |
| |
| |
Single Rotation | |
| |
| |
Double Rotation | |
| |
| |
Splay Trees | |
| |
| |
A Simple Idea (That Does Not Work) | |
| |
| |
Splaying | |
| |
| |
Tree Traversals (Revisited) | |
| |
| |
B-Trees | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
Hashing | |
| |
| |
General Idea | |
| |
| |
Hash Function | |
| |
| |
Separate Chaining | |
| |
| |
Open Addressing | |
| |
| |
Linear Probing | |
| |
| |
Quadratic Probing | |
| |
| |
Double Hashing | |
| |
| |
Rehashing | |
| |
| |
Extendible Hashing | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
Priority Queues (Heaps) | |
| |
| |
Model | |
| |
| |
Simple Implementations | |
| |
| |
Binary Heap | |
| |
| |
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 | |
| |
| |
Implementation of Binomial Queues | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
Sorting | |
| |
| |
Preliminaries | |
| |
| |
Insertion Sort | |
| |
| |
The Algorithm | |
| |
| |
Analysis of Insertion Sort | |
| |
| |
A Lower Bound for Simple Sorting Algorithms | |
| |
| |
Shellsort | |
| |
| |
Worst-Case Analysis of Shellsort | |
| |
| |
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 | |
| |
| |
Indirect Sorting | |
| |
| |
Vector<Comparable *> | |
| |
| |
Does Not Work | |
| |
| |
Smart Pointer Class | |
| |
| |
Overloading operator | |
| |
| |
Dereferencing a Pointer with * | |
| |
| |
Overloading the Type Conversion Operator | |
| |
| |
Implicit Type Conversions Are Everywhere | |
| |
| |
Dual-Direction Implicit Conversions Can Cause Ambiguities | |
| |
| |
Pointer Subtraction Is Legal | |
| |
| |
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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
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 NP-Completeness | |
| |
| |
Easy vs. Hard | |
| |
| |
The Class NP | |
| |
| |
NP-Complete Problems | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
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 | |
| |
| |
Summary | |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
| |
The Standard Template Library | |
| |
| |
Introduction | |
| |
| |
Basic STL Concepts | |
| |
| |
Header Files and the using Directive | |
| |
| |
Containers | |
| |
| |
iterator | |
| |
| |
Pairs | |
| |
| |
Function Objects | |
| |
| |
Unordered Sequences: vector and list | |
| |
| |
vector versus list | |
| |
| |
Stacks and Queues | |
| |
| |
Sets | |
| |
| |
Maps | |
| |
| |
Example: Generating a Concordance | |
| |
| |
STL Version | |
| |
| |
Version without Using the STL | |
| |
| |
Example: Shortest-Path Calculation | |
| |
| |
STL Implementation | |
| |
| |
Version without Using the STL | |
| |
| |
Other STL Features | |
| |
| |
| |
vector and string Classes | |
| |
| |
First-Class versus Second-Class Objects | |
| |
| |
vector Class | |
| |
| |
string Class | |
| |
| |
Index | |