本书是在第一版的基础上修订而成的。本书揭密了算法的设计与分析，以简单易懂的写作风格，介绍了各种算法技术，着重强调了算法分析。全书包括两大部分，“技术”部分介绍了设计和分析计算机算法的各种方法，“资源”部分给出了大量的参考资源，以及算法实现的各种资源。本书为英文影印版。

本书是算法设计畅销书的最新版本，是设计实用且高效算法的最全面指导书。本书揭密了算法的设计与分析，以简单易懂的写作风格，介绍了各种算法技术，着重强调了算法分析，全书包括两大部分，“技术”部分介绍了设计和分析计算机算法的各种方法，“资源”部分给出了大量的参考资源，以及算法实现的各种资源，此外，在作者的个人网址http：／／www.cs.sunysb.edu／～algorith／上还提供了各种教学资源和参考材料，这些资源对读者很有参考价值。

本书可以作为算法设计课程的主教材，也是程序人员、研究人员和学生的常备参考书。

 Ⅰ Practical Algorithm Design

1 Introduction to Algorithm Design

 1.1 Robot Tour Optimization

 1.2 Selecting the Right Jobs

 1.3 Reasoning about Correctness

 1.4 Modeling the Problem

 1.5 About the Wax Stories

 1.6 War Story: Psychic Modeling

 1.7 Exercises

2 Algorithm Analysis

 2.1 The RAM Model of Computation

 2.2 The Big Oh Notation

 2.3 Growth Rates and Dominance Relations

 2.4 Working with the Big Oh

 2.5 Reasoning About Efficiency

 2.6 Logarithms and Their Applications

 2.7 Properties of Logarithms

 2.8 War Story: Mystery of the Pyramids

 2.9 Advanced Analysis (*)

 2.10 Exercises

3 Data Structures

 3.1 Contiguous vs. Linked Data Structures

 3.2 Stacks and Queues

 3.3 Dictionaries

 3.4 Binary Search Trees

 3.5 Priority Queues

 3.6 War Story: Stripping Triangulations

 3.7 Hashing and Strings

 3.8 Specialized Data Structures

 3.9 War Story: String'em Up

 3.10 Exercises

4 Sorting and Searching

 4.1 Applications of Sorting

 4.2 Pragmatics of Sorting

 4.3 Heapsort: Fast Sorting via Data Structures

 4.4 War Story: Give me a Ticket on an Airplane

 4.5 Mergesort: Sorting by Divide-and-Conquer

 4.6 Quicksort: Sorting by Randomization

 4.7 Distribution Sort: Sorting via Bucketing

 4.8 War Story: Skiena for the Defense

 4.9 Binary Search and Related Algorithms

 4.10 Divide-and-Conquer

 4.11 Exercises

5 Graph Traversal

 5.1 Flavors of Graphs

 5.2 Data Structures for Graphs

 5.3 War Story: I was a Victim of Moore's Law

 5.4 War Story: Getting the Graph

 5.5 Traversing a Graph

 5.6 Breadth-First Search

 5.7 Applications of Breadth-First Search

 5.8 Depth-First Search

 5.9 Applications of Depth-First Search

 5.10 Depth-First Search on Directed Graphs

 5.11 Exercises

6 Weighted Graph Algorithms

 6.1 Minimum Spanning Trees

 6.2 War Story: Nothing but Nets

 6.3 Shortest Paths

 6.4 War Story: Dialing for Documents

 6.5 Network Flows and Bipartite Matching

 6.6 Design Graphs, Not Algorithms

 6.7 Exercises

7 Combinatorial Search and Heuristic Methods

 7.1 Backtracking

 7.2 Search Pruning

 7.3 Sudoku

 7.4 War Story: Covering Chessboards

 7.5 Heuristic Search Methods

 7.6 War Story: Only it is Not a Radio

 7.7 War Story: Annealing Arrays

 7.8 Other Heuristic Search Methods

 7.9 Parallel Algorithms

 7.10 War Story: Going Nowhere Fast

 7.11 Exercises

8 Dynamic Programming

 8.1 Caching vs. Computation

 8.2 Approximate String Matching

 8.3 Longest Increasing Sequence

 8.4 War Story: Evolution of the Lobster

 8.5 The Partition Problem

 8.6 Parsing Context-Free Grammars

 8.7 Limitations of Dynamic Programming: TSP

 8.8 War Story: What's Past is Prolog

 8.9 War Story: Text Compression for Bar Codes

 8.10 Exercises

9 Intractable Problems and Approximation Algorithms

 9.1 Problems and Reductions

 9.2 Reductions for Algorithms

 9.3 Elementary Hardness Reductions

 9.4 Satisfiability

 9.5 Creative Reductions

 9.6 The Art of Proving Hardness

 9.7 War Story: Hard Against the Clock

 9.8 War Story: And Then I Failed

 9.9 P vs. NP

 9.10 Dealing with NP-complete Problems

 9.11 Exercises

10 How to Design Algorithms

 Ⅱ The Hitchhiker's Guide to Algorithms

11 A Catalog of Algorithmic Problems

12 Data Structures

 12.1 Dictionaries

 12.2 Priority Queues

 12.3 Suffix Trees and Arrays

 12.4 Graph Data Structures

 12.5 Set Data Structures

 12.6 Kd-Trees

13 Numerical Problems

 13.1 Solving Linear Equations

 13.2 Bandwidth Reduction

 13.3 Matrix Multiplication

 13.4 Determinants and Permanents

 13.5 Constrained and Unconstrained Optimization

 13.6 Linear Programming

 13.7 Random Number Generation

 13.8 Factoring and Primality Testing

 13.9 Arbitrary-Precision Arithmetic

 13.10 Knapsack Problem

 13.11 Discrete Fourier Transform

14 Combinatorial Problems

 14.1 Sorting

 14.2 Searching

 14.3 Median and Selection

 14.4 Generating Permutations

 14.5 Generating Subsets

 14.6 Generating Partitions

 14.7 Generating Graphs

 14.8 Calendrical Calculations

 14.9 Job Scheduling

 14.10 Satisfiability

15 Graph Problems: Polynomial-Time

 15.1 Connected Components

 15.2 Topological Sorting

 15.3 Minimum Spanning Tree

 15.4 Shortest Path

 15.5 Transitive Closure and Reduction

 15.6 Matching

 15.7 Eulerian Cycle/Chinese Postman

 15.8 Edge and Vertex Connectivity

 15.9 Network Flow

 15.10 Drawing Graphs Nicely

 15.11 Drawing Trees

 15.12 Planarity Detection and Embedding

16 Graph Problems: Hard Problems

 16.1 Clique

 16.2 Independent Set

 16.3 Vertex Cover

 16.4 Traveling Salesman Problem

 16.5 Hamiltonian Cycle

 16.6 Graph Partition

 16.7 Vertex Coloring

 16.8 Edge Coloring

 16.9 Graph Isomorphism

 16.10 Steiner Tree

 16.11 Feedback Edge/Vertex Set

17 Computational Geometry

 17.1 Robust Geometric Primitives

 17.2 Convex Hull

 17.3 Triangulation

 17.4 Voronoi Diagrams

 17.5 Nearest Neighbor Search

 17.6 Range Search

 17.7 Point Location

 17.8 Intersection Detection

 17.9 Bin Packing

 17.10 Medial-Axis Transform

 17.11 Polygon Partitioning

 17.12 Simplifying Polygons

 17.13 Shape Similarity

 17.14 Motion Planning

 17.15 Maintaining Line Arrangements

 17.16 Minkowski Sum

18 Set and String Problems

 18.1 Set Cover

 18.2 Set Packing

 18.3 String Matching

 18.4 Approximate String Matching

 18.5 Text Compression

 18.6 Cryptography

 18.7 Finite State Machine Minimization

 18.8 Longest Common Substring/Subsequence

 18.9 Shortest Common Superstring

19 Algorithmic Resources

 19.1 Software Systems

 19.2 Data Sources

 19.3 Online Bibliographic Resources

 19.4 Professional Consulting Services

Bibliography