Preface | p. xv |
Introduction | p. 1 |
What's the Book About? | p. 1 |
Mathematics Review | p. 2 |
Exponents | p. 3 |
Logarithms | p. 3 |
Series | p. 4 |
Modular Arithmetic | p. 5 |
The P Word | p. 6 |
A Brief Introduction to Recursion | p. 7 |
C++ Classes | p. 11 |
Basic class Syntax | p. 12 |
Extra Constructor Syntax and Accessors | p. 12 |
Separation of Interface and Implementation | p. 15 |
vector and string | p. 17 |
C++ Details | p. 19 |
Pointers | p. 19 |
Parameter Passing | p. 21 |
Return Passing | p. 22 |
Reference Variables | p. 23 |
The Big Three: Destructor, Copy Constructor, operator= | p. 23 |
C-style Arrays and Strings | p. 26 |
Templates | p. 29 |
Function Templates | p. 29 |
Class Templates | p. 30 |
Object, Comparable, and an Example | p. 32 |
Function Objects | p. 34 |
Separate Compilation of Class Templates | p. 35 |
Using Matrices | p. 37 |
The Data Members, Constructor, and Basic Accessors | p. 37 |
operator[] | p. 37 |
Destructor, Copy Assignment, Copy Constructor | p. 39 |
Summary | p. 39 |
Exercises | p. 39 |
References | p. 41 |
Algorithm Analysis | p. 43 |
Mathematical Background | p. 43 |
Model | p. 46 |
What to Analyze | p. 46 |
Running Time Calculations | p. 49 |
A Simple Example | p. 49 |
General Rules | p. 50 |
Solutions for the Maximum Subsequence Sum Problem | p. 52 |
Logarithms in the Running Time | p. 58 |
Checking Your Analysis | p. 62 |
A Grain of Salt | p. 63 |
Summary | p. 63 |
Exercises | p. 64 |
References | p. 69 |
Lists, Stacks, and Queues | p. 71 |
Abstract Data Types (ADTs) | p. 71 |
The List ADT | p. 72 |
Simple Array Implementation of Lists | p. 72 |
Simple Linked Lists | p. 73 |
vector and list in the STL | p. 74 |
Iterators | p. 75 |
Example: Using erase on a List | p. 77 |
const_iterators | p. 77 |
Implementation of vector | p. 79 |
Implementation of list | p. 83 |
The Stack ADT | p. 94 |
Stack Model | p. 94 |
Implementation of Stacks | p. 95 |
Applications | p. 96 |
The Queue ADT | p. 104 |
Queue Model | p. 104 |
Array Implementation of Queues | p. 104 |
Applications of Queues | p. 106 |
Summary | p. 107 |
Exercises | p. 108 |
Trees | p. 113 |
Preliminaries | p. 113 |
Implementation of Trees | p. 114 |
Tree Traversals with an Application | p. 115 |
Binary Trees | p. 119 |
Implementation | p. 120 |
An Example: Expression Trees | p. 121 |
The Search Tree ADT-Binary Search Trees | p. 124 |
contains | p. 125 |
findMin and findMax | p. 125 |
insert | p. 129 |
remove | p. 130 |
Destructor and Copy Assignment Operator | p. 132 |
Average-Case Analysis | p. 133 |
AVL Trees | p. 136 |
Single Rotation | p. 139 |
Double Rotation | p. 142 |
Splay Trees | p. 149 |
A Simple Idea (That Does Not Work) | p. 150 |
Splaying | p. 152 |
Tree Traversals (Revisited) | p. 158 |
B-Trees | p. 159 |
Sets and Maps in the Standard Library | p. 165 |
Sets | p. 165 |
Maps | p. 166 |
Implementation of set and map | p. 167 |
An Example That Uses Several Maps | p. 168 |
Summary | p. 174 |
Exercises | p. 174 |
References | p. 181 |
Hashing | p. 185 |
General Idea | p. 185 |
Hash Function | p. 186 |
Separate Chaining | p. 188 |
Hash Tables Without Linked Lists | p. 192 |
Linear Probing | p. 193 |
Quadratic Probing | p. 195 |
Double Hashing | p. 199 |
Rehashing | p. 200 |
Hash Tables in the Standard Library | p. 204 |
Extendible Hasing | p. 204 |
Summary | p. 207 |
Exercises | p. 208 |
References | p. 211 |
Priority Queues (Heaps) | p. 213 |
Model | p. 213 |
Simple Implementations | p. 214 |
Binary Heap | p. 215 |
Structure Property | p. 215 |
Heap-Order Property | p. 216 |
Basic Heap Operations | p. 217 |
Other Heap Operations | p. 220 |
Applications of Priority Queues | p. 225 |
The Selection Problem | p. 226 |
Event Simulation | p. 227 |
d-Heaps | p. 228 |
Leftist Heaps | p. 229 |
Leftist Heap Property | p. 229 |
Leftist Heap Operations | p. 230 |
Skew Heaps | p. 235 |
Binomial Queues | p. 239 |
Binomial Queue Structure | p. 240 |
Binomial Queue Operations | p. 241 |
Implementation of Binomial Queues | p. 244 |
Priority Queues in the Standard Library | p. 251 |
Summary | p. 251 |
Exercises | p. 251 |
References | p. 257 |
Sorting | p. 261 |
Preliminaries | p. 261 |
Insertion Sort | p. 262 |
The Algorithm | p. 262 |
STL Implementation of Insertion Sort | p. 263 |
Analysis of Insertion Sort | p. 264 |
A Lower Bound for Simple Sorting Algorithms | p. 265 |
Shellsort | p. 266 |
Worst-Case Analysis of Shellsort | p. 268 |
Heapsort | p. 270 |
Analysis of Heapsort | p. 272 |
Mergesort | p. 274 |
Analysis of Mergesort | p. 276 |
Quicksort | p. 279 |
Picking the Pivot | p. 280 |
Partitioning Strategy | p. 282 |
Small Arrays | p. 284 |
Actual Quicksort Routines | p. 284 |
Analysis of Quicksort | p. 287 |
A Linear-Expected-Time Algorithm for Selection | p. 290 |
Indirect Sorting | p. 292 |
vector[left angle bracket]Comparable*[right angle bracket] Does Not Work | p. 295 |
Smart Pointer Class | p. 295 |
Overloading operator[left angle bracket] | p. 295 |
Dereferencing a Pointer with * | p. 295 |
Overloading the Type Conversion Operator | p. 295 |
Implicit Type Conversions Are Everywhere | p. 296 |
Dual-Direction Implicit Conversions Can Cause Ambiguities | p. 296 |
Pointer Subtraction Is Legal | p. 297 |
A General Lower Bound for Sorting | p. 297 |
Decision Trees | p. 297 |
Bucket Sort | p. 299 |
External Sorting | p. 300 |
Why We Need New Algorithms | p. 300 |
Model for External Sorting | p. 300 |
The Simple Algorithm | p. 301 |
Multiway Merge | p. 302 |
Polyphase Merge | p. 303 |
Replacement Selection | p. 304 |
Summary | p. 305 |
Exercises | p. 306 |
References | p. 311 |
The Disjoint Set Class | p. 315 |
Equivalence Relations | p. 315 |
The Dynamic Equivalence Problem | p. 316 |
Basic Data Structure | p. 317 |
Smart Union Algorithms | p. 321 |
Path Compression | p. 324 |
Worst Case for Union-by-Rank and Path Compression | p. 325 |
Analysis of the Union/Find Algorithm | p. 326 |
An Application | p. 331 |
Summary | p. 334 |
Exercises | p. 335 |
References | p. 336 |
Graph Algorithms | p. 339 |
Definitions | p. 339 |
Representation of Graphs | p. 340 |
Topological Sort | p. 342 |
Shortest-Path Algorithms | p. 345 |
Unweighted Shortest Paths | p. 347 |
Dijkstra's Algorithm | p. 351 |
Graphs with Negative Edge Costs | p. 360 |
Acyclic Graphs | p. 360 |
All-Pairs Shortest Path | p. 364 |
Shortest Path Example | p. 365 |
Network Flow Problems | p. 367 |
A Simple Maximum-Flow Algorithm | p. 367 |
Minimum Spanning Tree | p. 372 |
Prim's Algorithm | p. 373 |
Kruskal's Algorithm | p. 376 |
Applications of Depth-First Search | p. 378 |
Undirected Graphs | p. 379 |
Biconnectivity | p. 381 |
Euler Circuits | p. 385 |
Directed Graphs | p. 388 |
Finding Strong Components | p. 390 |
Introduction to NP-Completeness | p. 392 |
Easy vs. Hard | p. 392 |
The Class NP | p. 393 |
NP-Complete Problems | p. 394 |
Summary | p. 396 |
Exercises | p. 396 |
References | p. 404 |
Algorithm Design Techniques | p. 409 |
Greedy Algorithms | p. 409 |
A Simple Scheduling Problem | p. 410 |
Huffman Codes | p. 413 |
Approximate Bin Packing | p. 419 |
Divide and Conquer | p. 427 |
Running Time of Divide and Conquer Algorithms | p. 428 |
Closest-Points Problem | p. 430 |
The Selection Problem | p. 435 |
Theoretical Improvements for Arithmetic Problems | p. 438 |
Dynamic Programming | p. 442 |
Using a Table Instead of Recursion | p. 442 |
Ordering Matrix Multiplications | p. 444 |
Optimal Binary Search Tree | p. 447 |
All-Pairs Shortest Path | p. 451 |
Randomized Algorithms | p. 454 |
Random Number Generators | p. 455 |
Skip Lists | p. 459 |
Primality Testing | p. 461 |
Backtracking Algorithms | p. 464 |
The Turnpike Reconstruction Problem | p. 465 |
Games | p. 469 |
Summary | p. 475 |
Exercises | p. 475 |
References | p. 485 |
Amortized Analysis | p. 491 |
An Unrelated Puzzle | p. 492 |
Binomial Queues | p. 492 |
Skew Heaps | p. 497 |
Fibonacci Heaps | p. 499 |
Cutting Nodes in Leftist Heaps | p. 500 |
Lazy Merging for Binomial Queues | p. 502 |
The Fibonacci Heap Operations | p. 506 |
Proof of the Time Bound | p. 506 |
Splay Trees | p. 509 |
Summary | p. 513 |
Exercises | p. 513 |
References | p. 515 |
Advanced Data Structures and Implementation | p. 517 |
Top-Down Splay Trees | p. 517 |
Red-Black Trees | p. 525 |
Bottom-Up Insertion | p. 526 |
Top-Down Red-Black Trees | p. 527 |
Top-Down Deletion | p. 531 |
Deterministic Skip Lists | p. 535 |
AA-Trees | p. 540 |
Treaps | p. 547 |
k-d Trees | p. 549 |
Pairing Heaps | p. 553 |
Summary | p. 558 |
Exercises | p. 558 |
References | p. 563 |
Separate Compilation of Class Templates | p. 567 |
Everything in the Header | p. 568 |
Explicit Instantiation | p. 568 |
The export Directive | p. 570 |
Index | p. 571 |
Table of Contents provided by Ingram. All Rights Reserved. |