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. |