| |
| |
| Preface | |
| |
| |
| |
| 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= | |
| |
| |
| |
| C-style Arrays and Strings | |
| |
| |
| |
| Templates | |
| |
| |
| |
| Function Templates | |
| |
| |
| |
| Class Templates | |
| |
| |
| |
| Object, Comparable, and an Example | |
| |
| |
| |
| Function Objects | |
| |
| |
| |
| Separate Compilation of Class Templates | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Simple Linked Lists | |
| |
| |
| |
| vector and list in the STL | |
| |
| |
| |
| Iterators | |
| |
| |
| |
| Example: Using erase on a List | |
| |
| |
| |
| const_iterators | |
| |
| |
| |
| Implementation of vector | |
| |
| |
| |
| Implementation of list | |
| |
| |
| |
| 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 | |
| |
| |
| |
| contains | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Sets and Maps in the Standard Library | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Maps | |
| |
| |
| |
| Implementation of set and map | |
| |
| |
| |
| An Example That Uses Several Maps | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Hashing | |
| |
| |
| |
| General Idea | |
| |
| |
| |
| Hash Function | |
| |
| |
| |
| Separate Chaining | |
| |
| |
| |
| Hash Tables Without Linked Lists | |
| |
| |
| |
| Linear Probing | |
| |
| |
| |
| Quadratic Probing | |
| |
| |
| |
| Double Hashing | |
| |
| |
| |
| Rehashing | |
| |
| |
| |
| Hash Tables in the Standard Library | |
| |
| |
| |
| Extendible Hasing | |
| |
| |
| 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 | |
| |
| |
| |
| Priority Queues in the Standard Library | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Sorting | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Insertion Sort | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| STL Implementation of Insertion Sort | |
| |
| |
| |
| 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[left angle bracket]Comparable*[right angle bracket] Does Not Work | |
| |
| |
| |
| Smart Pointer Class | |
| |
| |
| |
| Overloading operator[left angle bracket] | |
| |
| |
| |
| 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 Class | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Shortest Path Example | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Separate Compilation of Class Templates | |
| |
| |
| |
| Everything in the Header | |
| |
| |
| |
| Explicit Instantiation | |
| |
| |
| |
| The export Directive | |
| |
| |
| Index | |