| |

| |

New to the Third Edition | |

| |

| |

Preface | |

| |

| |

| |

Introduction | |

| |

| |

| |

What Is an Algorithm? | |

| |

| |

Exercises 1.1 | |

| |

| |

| |

Fundamentals of Algorithmic Problem Solving | |

| |

| |

Understanding the Problem | |

| |

| |

Ascertaining the Capabilities of the Computational Device | |

| |

| |

Choosing between Exact and Approximate Problem Solving | |

| |

| |

Algorithm Design Techniques | |

| |

| |

Designing an Algorithm and Data Structures | |

| |

| |

Methods of Specifying an Algorithm | |

| |

| |

Proving an Algorithm's Correctness | |

| |

| |

Analyzing an Algorithm | |

| |

| |

Coding an Algorithm | |

| |

| |

Exercises 1.2 | |

| |

| |

| |

Important Problem Types | |

| |

| |

Sorting | |

| |

| |

Searching | |

| |

| |

String Processing | |

| |

| |

Graph Problems | |

| |

| |

Combinatorial Problems | |

| |

| |

Geometric Problems | |

| |

| |

Numerical Problems | |

| |

| |

Exercises 1.3 | |

| |

| |

| |

Fundamental Data Structures | |

| |

| |

Linear Data Structures | |

| |

| |

Graphs | |

| |

| |

Trees | |

| |

| |

Sets and Dictionaries | |

| |

| |

Exercises 1.4 | |

| |

| |

Summary | |

| |

| |

| |

Fundamentals of the Analysis of Algorithm Efficiency | |

| |

| |

| |

The Analysis Framework | |

| |

| |

Measuring an Input's Size | |

| |

| |

Units for Measuring Running Time | |

| |

| |

Orders of Growth | |

| |

| |

Worst-Case, Best-Case, and Average-Case Efficiencies | |

| |

| |

Recapitulation of the Analysis Framework | |

| |

| |

Exercises 2.1 | |

| |

| |

| |

Asymptotic Notations and Basic Efficiency Classes | |

| |

| |

Informal Introduction | |

| |

| |

O-notation | |

| |

| |

-notation | |

| |

| |

-notation | |

| |

| |

Useful Property Involving the Asymptotic Notations | |

| |

| |

Using Limits for Comparing Orders of Growth | |

| |

| |

Basic Efficiency Classes | |

| |

| |

Exercises 2.2 | |

| |

| |

| |

Mathematical Analysis of Nonrecursive Algorithms | |

| |

| |

Exercises 2.3 | |

| |

| |

| |

Mathematical Analysis of Recursive Algorithms | |

| |

| |

Exercises 2.4 | |

| |

| |

| |

Example: Computing the nth Fibonacci Number | |

| |

| |

Exercises 2.5 | |

| |

| |

| |

Empirical Analysis of Algorithms | |

| |

| |

Exercises 2.6 | |

| |

| |

| |

Algorithm Visualization | |

| |

| |

Summary | |

| |

| |

| |

Brute Force and Exhaustive Search | |

| |

| |

| |

Selection Sort and Bubble Sort | |

| |

| |

Selection Sort | |

| |

| |

Bubble Sort | |

| |

| |

Exercises 3.1 | |

| |

| |

| |

Sequential Search and Brute-Force String Matching | |

| |

| |

Sequential Search | |

| |

| |

Brute-Force String Matching | |

| |

| |

Exercises 3.2 | |

| |

| |

| |

Closest-Pair and Convex-Hull Problems by Brute Force | |

| |

| |

Closest-Pair Problem | |

| |

| |

Convex-Hull Problem | |

| |

| |

Exercises 3.3 | |

| |

| |

| |

Exhaustive Search | |

| |

| |

Traveling Salesman Problem | |

| |

| |

Knapsack Problem | |

| |

| |

Assignment Problem | |

| |

| |

Exercises 3.4 | |

| |

| |

| |

Depth-First Search and Breadth-First Search | |

| |

| |

Depth-First Search | |

| |

| |

Breadth-First Search | |

| |

| |

Exercises 3.5 | |

| |

| |

Summary | |

| |

| |

| |

Decrease-and-Conquer | |

| |

| |

| |

Insertion Sort | |

| |

| |

Exercises 4.1 | |

| |

| |

| |

Topological Sorting | |

| |

| |

Exercises 4.2 | |

| |

| |

| |

Algorithms for Generating Combinatorial Objects | |

| |

| |

Generating Permutations | |

| |

| |

Generating Subsets | |

| |

| |

Exercises 4.3 | |

| |

| |

| |

Decrease-by-a-Constant-Factor Algorithms | |

| |

| |

Binary Search | |

| |

| |

Fake-Coin Problem | |

| |

| |

Russian Peasant Multiplication | |

| |

| |

Josephus Problem | |

| |

| |

Exercises 4.4 | |

| |

| |

| |

Variable-Size-Decrease Algorithms | |

| |

| |

Computing a Median and the Selection Problem | |

| |

| |

Interpolation Search | |

| |

| |

Searching and Insertion in a Binary Search Tree | |

| |

| |

The Game of Nim | |

| |

| |

Exercises 4.5 | |

| |

| |

Summary | |

| |

| |

| |

Divide-and-Conquer | |

| |

| |

| |

Mergesort | |

| |

| |

Exercises 5.1 | |

| |

| |

| |

Quicksort | |

| |

| |

Exercises 5.2 | |

| |

| |

| |

Binary Tree Traversals and Related Properties | |

| |

| |

Exercises 5.3 | |

| |

| |

| |

Multiplication of Large Integers and Strassen's Matrix Multiplication | |

| |

| |

Multiplication of Large Integers | |

| |

| |

Strassen's Matrix Multiplication | |

| |

| |

Exercises 5.4 | |

| |

| |

| |

The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer | |

| |

| |

The Closest-Pair Problem | |

| |

| |

Convex-Hull Problem | |

| |

| |

Exercises 5.5 | |

| |

| |

Summary | |

| |

| |

| |

Transform-and-Conquer | |

| |

| |

| |

Presorting | |

| |

| |

Exercises 6.1 | |

| |

| |

| |

Gaussian Elimination | |

| |

| |

LU Decomposition | |

| |

| |

Computing a Matrix Inverse | |

| |

| |

Computing a Determinant | |

| |

| |

Exercises 6.2 | |

| |

| |

| |

Balanced Search Trees | |

| |

| |

AVL Trees | |

| |

| |

| |

Trees | |

| |

| |

Exercises 6.3 | |

| |

| |

| |

Heaps and Heapsort | |

| |

| |

Notion of the Heap | |

| |

| |

Heapsort | |

| |

| |

Exercises 6.4 | |

| |

| |

| |

Horner's Rule and Binary Exponentiation | |

| |

| |

Horner's Rule | |

| |

| |

Binary Exponentiation | |

| |

| |

Exercises 6.5 | |

| |

| |

| |

Problem Reduction | |

| |

| |

Computing the Least Common Multiple | |

| |

| |

Counting Paths in a Graph | |

| |

| |

Reduction of Optimization Problems | |

| |

| |

Linear Programming | |

| |

| |

Reduction to Graph Problems | |

| |

| |

Exercises 6.6 | |

| |

| |

Summary | |

| |

| |

| |

Space and Time Trade-Offs | |

| |

| |

| |

Sorting by Counting | |

| |

| |

Exercises 7.1 | |

| |

| |

| |

Input Enhancement in String Matching | |

| |

| |

Horspool's Algorithm | |

| |

| |

Boyer-Moore Algorithm | |

| |

| |

Exercises 7.2 | |

| |

| |

| |

Hashing | |

| |

| |

Open Hashing (Separate Chaining) | |

| |

| |

Closed Hashing (Open Addressing) | |

| |

| |

Exercises 7.3 | |

| |

| |

| |

B-Trees | |

| |

| |

Exercises 7.4 | |

| |

| |

Summary | |

| |

| |

| |

Dynamic Programming | |

| |

| |

| |

Three Basic Examples | |

| |

| |

Exercises 8.1 | |

| |

| |

| |

The Knapsack Problem and Memory Functions | |

| |

| |

Memory Functions | |

| |

| |

Exercises 8.2 | |

| |

| |

| |

Optimal Binary Search Trees | |

| |

| |

Exercises 8.3 | |

| |

| |

| |

Warshall's and Floyd's Algorithms | |

| |

| |

Warshall's Algorithm | |

| |

| |

Floyd's Algorithm for the All-Pairs Shortest-Paths Problem | |

| |

| |

Exercises 8.4 | |

| |

| |

Summary | |

| |

| |

| |

Greedy Technique | |

| |

| |

| |

Prim's Algorithm | |

| |

| |

Exercises 9.1 | |

| |

| |

| |

Kruskal's Algorithm | |

| |

| |

Disjoint Subsets and Union-Find Algorithms | |

| |

| |

Exercises 9.2 | |

| |

| |

| |

Dijkstra's Algorithm | |

| |

| |

Exercises 9.3 | |

| |

| |

| |

Huffman Trees and Codes | |

| |

| |

Exercises 9.4 | |

| |

| |

Summary | |

| |

| |

| |

Iterative Improvement | |

| |

| |

| |

The Simplex Method | |

| |

| |

Geometric Interpretation of Linear Programming | |

| |

| |

An Outline of the Simplex Method | |

| |

| |

Further Notes on the Simplex Method | |

| |

| |

Exercises 10.1 | |

| |

| |

| |

The Maximum-Flow Problem | |

| |

| |

Exercises 10.2 | |

| |

| |

| |

Maximum Matching in Bipartite Graphs | |

| |

| |

Exercises 10.3 | |

| |

| |

| |

The Stable Marriage Problem | |

| |

| |

Exercises 10.4 | |

| |

| |

Summary | |

| |

| |

| |

Limitations of Algorithm Power | |

| |

| |

| |

Lower-Bound Arguments | |

| |

| |

Trivial Lower Bounds | |

| |

| |

Information-Theoretic Arguments | |

| |

| |

Adversary Arguments | |

| |

| |

Problem Reduction | |

| |

| |

Exercises 11.1 | |

| |

| |

| |

Decision Trees | |

| |

| |

Decision Trees for Sorting | |

| |

| |

Decision Trees for Searching a Sorted Array | |

| |

| |

Exercises 11.2 | |

| |

| |

| |

P, NP, and NP-Complete Problems | |

| |

| |

P and NP Problems | |

| |

| |

NP-Complete Problems | |

| |

| |

Exercises 11.3 | |

| |

| |

| |

Challenges of Numerical Algorithms | |

| |

| |

Exercises 11.4 | |

| |

| |

Summary | |

| |

| |

| |

Coping with the Limitations of Algorithm Power | |

| |

| |

| |

Backtracking | |

| |

| |

n-Queens Problem | |

| |

| |

Hamiltonian Circuit Problem | |

| |

| |

Subset-Sum Problem | |

| |

| |

General Remarks | |

| |

| |

Exercises 12.1 | |

| |

| |

| |

Branch-and-Bound | |

| |

| |

Assignment Problem | |

| |

| |

Knapsack Problem | |

| |

| |

Traveling Salesman Problem | |

| |

| |

Exercises 12.2 | |

| |

| |

| |

Approximation Algorithms for NP-Hard Problems | |

| |

| |

Approximation Algorithms for the Traveling Salesman Problem | |

| |

| |

Approximation Algorithms for the Knapsack Problem | |

| |

| |

Exercises 12.3 | |

| |

| |

| |

Algorithms for Solving Nonlinear Equations | |

| |

| |

Bisection Method | |

| |

| |

Method of False Position | |

| |

| |

Newton's Method | |

| |

| |

Exercises 12.4 | |

| |

| |

Summary | |

| |

| |

Epilogue | |

| |

| |

| |

| |

| |

Useful Formulas for the Analysis of Algorithms | |

| |

| |

Properties of Logarithms | |

| |

| |

Combinatorics | |

| |

| |

Important Summation Formulas | |

| |

| |

Sum Manipulation Rules | |

| |

| |

Approximation of a Sum by a Definite Integral | |

| |

| |

Floor and Ceiling Formulas | |

| |

| |

Miscellaneous | |

| |

| |

| |

| |

| |

Short Tutorial on Recurrence Relations | |

| |

| |

Sequences and Recurrence Relations | |