| |

| |

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