算法设计与分析基础 : 第3版

New to the Third Edition xvii

Preface xix

1Introduction

1.1 What Is an Algorithm?

Exercises 1.1

1.2 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

1.3 Important Problem Types

Sorting

Searching

String Processing

Graph Problems

Combinatorial Problems

Geometric Problems

Numerical Problems

Exercises 1.3

1.4 Fundamental Data Structures

Linear Data Structures

Graphs

Trees

Sets and Dictionaries

Exerises 1.4

Summary

2 Fundamentals of the Analysis of Algorithm Efficiency

2.1 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

2.2 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

2.3 Mathematical Analysis of Nonrecursive Algorithms

Exercises 2.3

2.4 Mathematical Analysis of Recursive Algorithms

Exercises 2.4

2.5 Example: Computing the nth Fibonacci Number

Exercises 2.5

2.6 Empirical Analysis of Algorithms

Exercises 2.6

2.7 Algorithm Visualization

Summary

3 Brute Force and Exhaustive Search

3.1 Selection Sort and Bubble Sort

Selection Sort

Bubble Sort

Exercises 3.1

3.2 Sequential Search and Brute-Force String Matching

Sequential Search

Brute-Force String Matching

Exercises 3.2

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

Closest-Pair Problem

Convex-Hull Problem

Exercises 3.3

3.4 Exhaustive Search

Traveling Salesman Problem

Knapsack Problem

Assignment Problem

Exercises 3.4

3.5 Depth-First Search and Breadth-First Search

Depth-First Search

Breadth-First Search

Exercises 3.5

Summary

4 Decrease-and-Conquer

4.1 Insertion Sort

Exercises 4.1

4.2 Topological Sorting

Exercises 4.2

4.3 Algorithms for Generating Combinatorial Objects

Generating Permutations

Generating Subsets

Exercises 4.3

4.4 Decrease-by-a-Constant-Factor Algorithms

Binary Search

Fake-Coin Problem

Russian Peasant Multiplication

Josephus Problem

Exercises 4.4

4.5 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

5 Divide-and-Conquer

5.1 Mergesort

Exercises 5.1

5.2 Quicksort

Exercises 5.2

5.3 Binary Tree Traversals and Related Properties

Exercises 5.3

5.4 Multiplication of Large Integers and

Strassen's Matrix Multiplication

Multiplication of Large Integers

Strassen's Matrix Multiplication

Exercises 5.4

5.5 The Closest-Pair and Convex-Hull Problems

by Divide-and-Conquer

The Closest-Pair Problem

Convex-Hull Problem

Exercises 5.5

Summary

6 Transform-and-Conquer

6.1 Presorting

Exercises 6.1

6.2 Gaussian Elimination

LU Decomposition

Computing a Matrix Inverse

Computing a Determinant

Exercises 6.2

6.3 Balanced Search Trees

AVL Trees

2-3 Trees

Exercises 6.3

6.4 Heaps and Heapsort

Notion of the Heap

Heapsort

Exercises 6.4

6.5 Horner's Rule and Binary Exponentiation

Horner's Rule

Binary Exponentiation

Exercises 6.5

6.6 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

7 Space and Time Trade-Offs

7.1 Sorting by Counting

Exercises 7.1

7.2 Input Enhancement in String Matching

Horspool's Algorithm

Boyer-Moore Algorithm

Exercises 7.2

7.3 Hashing

Open Hashing (Separate Chaining)

Closed Hashing (Open Addressing)

Exercises 7.3

7.4 B-Trees

Exercises 7.4

Summary

8 Dynamic Programming

8.1 Three Basic Examples

Exercises 8.1

8.2 The Knapsack Problem and Memory Functions

Memory Functions

Exercises 8.2

8.3 Optimal Binary Search Trees

Exercises 8.3

8.4 Warshall's and Floyd's Algorithms

Warshall's Algorithm

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

Exercises 8.4

Summary

9 Greedy Technique

9.1 Prim's Algorithm

Exercises 9.1

9.2 Kruskal's Algorithm

Disjoint Subsets and Union-Find Algorithms

Exercises 9.2

9.3 Dijkstra's Algorithm

Exercises 9.3

9.4 Huffman Trees and Codes

Exercises 9.4

Summary

10 Iterative Improvement

10.1 The Simplex Method

Geometric Interpretation of Linear Programming

An Outline of the Simplex Method

Further Notes on the Simplex Method

Exercises 10.1

10.2 The Maximum-Flow Problem

Exercises 10.2

10.3 Maximum Matching in Bipartite Graphs

Exercises 10.3

10.4 The Stable Marriage Problem

Exercises 10.4

Summary

11 Limitations of Algorithm Power

11.1 Lower-Bound Arguments

Trivial Lower Bounds

Information-Theoretic Arguments

Adversary Arguments

Problem Reduction

Exercises 11.1

11.2 Decision Trees

Decision Trees for Sorting

Decision Trees for Searching a Sorted Array

Exercises 11.2

11.3 P, NP, and NP-Complete Problems

P and NP Problems

NP-Complete Problems

Exercises 11.3

11.4 Challenges of Numerical Algorithms

Exercises 11.4

Summary

12 Coping with the Limitations of Algorithm Power

12.1 Backtracking

n-Queens Problem

Hamiltonian Circuit Problem

Subset-Sum Problem

General Remarks

Exercises 12.1

12.2 Branch-and-Bound

Assignment Problem

Knapsack Problem

Traveling Salesman Problem

Exercises 12.2

12.3 Approximation Algorithms for NP-Hard Problems

Approximation Algorithms for the Traveling Salesman Problem

Approximation Algorithms for the Knapsack Problem

Exercises 12.3

12.4 Algorithms for Solving Nonlinear Equations

Bisection Method

Method of False Position

Newton's Method

Exercises 12.4

Summary

Epilogue

APPENDIX A

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

APPENDIX B

Short Tutorial on Recurrence Relations

Sequences and Recurrence Relations

Methods for Solving Recurrence Relations

Common Recurrence Types in Algorithm Analysis

References

Hints to Exercises

Index

《算法设计与分析基础 （第3版）（影印版）》在讲述算法设计技术时采用了新的分类方法，在讨论分析方法时条分缕析，形成了连贯有序、耳目一新的风格。为便于学生掌握，本书涵盖算法入门课程的全部内容，更注重对概念(而非形式)的理解。书中通过一些流行的谜题来激发学生的兴趣，帮助他们加强和提高解决算法问题的能力。每章小结、习题提示和详细解答，形成了非常鲜明的教学特色。

历经十年数百所高校教学实践的算法入门经典。算法是思维的艺术，是数学之美的完美体现，是计算机和信息科学的灵魂，更是优秀程序员的安身立命之本。《算法设计与分析基础 (第3版）（影印版）》将算法视为解决问题的工具，通过作者独创的、具有里程碑意义的新型分类法弥补了传统算法设计技术分类法的缺陷，用深入浅出的语言和新颖的实例与谜题，诠释了何为算法、算法的分类、算法幕后的思想、算法的效率，抽丝剥茧、条分缕析地探索了算法设计与分析过程。