算法设计技巧与分析（英文版） (2009 年度畅销榜NO.2805 )

本书由World Scientific出版，它是以国际著名算法专家，我国台湾出身的李德财教授所主编的系列丛书——Lecture Notes Series on Computing——中的一本。该书组织简明、概括，且包含当前市面上算法书较少涉及的概率算法和近似算法的基本内容，是一本适合本科学生算法的好书。\r\n\r\n该书涉及及数据结构的部分较少，即使有一些，表述也很快与算法中比较复杂的集合查找和合并运算等相结合，使读者不会感到和已经学过的数据结构相重复。这比较适合中国大学计算机系中数据结构和算法分成两门开设的实际状况。\r\n
\r\n

Preface \r\n\r\n PART 1 Basic Concepts and Introduction to \r\n\r\n Algorithms \r\n\r\n Chapter 1 Basic Concepts in Algorithmic Analysis \r\n\r\n 1.1 Introduction \r\n\r\n l.2 Historical BaCkground \r\n\r\n 1.3 Binary Search \r\n\r\n 1.3.1 Analysis of the binary search algorithm \r\n\r\n 1.4 Merging Two Sorted Lists \r\n\r\n 1.5 Selectinn Sort \r\n\r\n 1.6 Insertion Sort \r\n\r\n 1.7 Bottom-Up Merge Sorting \r\n\r\n 1.7.1 Analysis of bottom-up merge sorting \r\n\r\n 1.8 Time Complexity \r\n\r\n 1.8.1 Order of growth \r\n\r\n 1.8.2 The O-notation \r\n\r\n 1.8.3 The fl-notation \r\n\r\n l.8.4 The e-notation \r\n\r\n 1.8.5 MamPles \r\n\r\n 1.8.6 Complekity classes and the o-notation \r\n\r\n 1.9 Space Complexity \r\n\r\n 1.10 Optimal Algorithms \r\n\r\n \r\n\r\n \r\n\r\n 1.1l How to Bstimate the Running Time of an Algorithm \r\n\r\n 1.l1.1 Couliting the number of forrations \r\n\r\n l.1l.2 Counting the frequency of basic operatha \r\n\r\n 1.1l.3 Using recurrence relations \r\n\r\n 1.l2 Worst case and average case analysis \r\n\r\n l.12.1 Wofst case analysis \r\n\r\n 1.12.2 Average case analysis \r\n\r\n l.13 Amedised Analyais \r\n\r\n 1.14 Input Sise and Problem Instance \r\n\r\n 1.15 Exercises \r\n\r\n 1.16 Bibiographic Notes \r\n\r\n Chapter 2 Mathematical Preliminaries \r\n\r\n 2.1 Sots, Reations and Annctions \r\n\r\n 2.1.1 sets \r\n\r\n 2.1.2 ffelations \r\n\r\n 2.1.2.l Equivalence relations \r\n\r\n 2.1.3 Thnctions \r\n\r\n 2.2 Proof Mehods \r\n\r\n 2.2.1 Direct proof \r\n\r\n 2.2.2 Indirect proof \r\n\r\n 2.2.3 Proof by colltradiction \r\n\r\n 2.2.4 Proof by cotillterexample \r\n\r\n 2.2.5 Mathematical induction \r\n\r\n 2.3 Logarithms \r\n\r\n 2.4 Floor and Ceiling Tunctions \r\n\r\n 2.5 Factorial and Binomial Coefficients \r\n\r\n 2.5.1 Factorials \r\n\r\n 2.5.2 Bintalal coefficients \r\n\r\n 2.6 The Pigeonhole Principle \r\n\r\n 2.7 Summations \r\n\r\n 2.7.1 Approkimation of summations by integration \r\n\r\n 2.8 Recurrence Relations \r\n\r\n 2.8.1 Solution of linear homogeneous recurrences \r\n\r\n 2.8.2 Solution of inhomogeneous recurrences \r\n\r\n 2.8.3 Solation of divide-and-conquer recurrence \r\n\r\n 2.8.3.1 Expanding the recurrence \r\n\r\n 2.8.3.2 Sutistitution \r\n\r\n 2.8.3.3 Change of variables \r\n\r\n 2.9 Exercises \r\n\r\n Chapter 3 Data Structures \r\n\r\n 3.1 Introdction \r\n\r\n 3.2 Linked Lists \r\n\r\n 3.2.1 Stacks ana queues \r\n\r\n 3.3 Graphs \r\n\r\n 3.3.1 Representation of graphs \r\n\r\n 3.3.2 planar graphs \r\n\r\n 3.4 Trees \r\n\r\n 3.5 Rooted Trees \r\n\r\n 3.5.1 Tree traversals \r\n\r\n 3.6 Binary Trees \r\n\r\n 3.6.l Some quantitative aspects of binary trees \r\n\r\n 3.6.2 Binary search trees \r\n\r\n 3.7 Exercises \r\n\r\n 3.8 Blbliographic Notes \r\n\r\n Chapter 4 Heaps and the Disjoint Sets Data Structure \r\n\r\n 4.l Iotroduction \r\n\r\n 4.2 Heaps \r\n\r\n 4.2.1 Operations on heaps \r\n\r\n 4.2.2 Creating a heap \r\n\r\n 4.2.3 Heapsort \r\n\r\n 4.2.4 Min and max heaps \r\n\r\n 4.3 Disjoint Sets Data Structures \r\n\r\n 4.3.1 The union by rank heuristic \r\n\r\n 4.3.2 Path compression \r\n\r\n 4.3.3 The union-find algorithms \r\n\r\n 4.3.4 Analysis of the uninn-find algorithms \r\n\r\n 4.4 Exercises \r\n\r\n 4.5 Bibliographic Notes \r\n\r\n PART 2 Techniques Based on Recursion \r\n\r\n Chapter 5 Induction \r\n\r\n \r\n\r\n \r\n\r\n 5.1 Introduction \r\n\r\n 5.2 Two Simple Examples \r\n\r\n 5.2.1 Selection sort \r\n\r\n 5.2.2 Insertion sort \r\n\r\n 5.3 Tadix Sort \r\n\r\n 5.4 Integer Exponentiation \r\n\r\n 5.5 Evaluating Polynomials (Horner's Rule) \r\n\r\n 5.6 Generating Permutations \r\n\r\n 5.6.1 The first algorithm \r\n\r\n 5.6.2 The second algorithm \r\n\r\n 5.7 Finding the Majority Element \r\n\r\n 5.8 Exercises \r\n\r\n 5.9 Bibliographic Notes \r\n\r\n Chapter 6 Divide and Conquer \r\n\r\n 6.1 Introduction \r\n\r\n 6.2 Binary Search \r\n\r\n 6.3 Mergesort \r\n\r\n 6.3.1 How the algorithm works \r\n\r\n 6.3.2 Analysis of the mergesort algorithm \r\n\r\n 6.4 The Divide and Conquer Paradigm \r\n\r\n 6.5 Selection: Finding the Median and the kth Smallest Element \r\n\r\n 6.5.l Analysis of the selection algorithm \r\n\r\n 6.6 Quicksort \r\n\r\n 6.6.1 A partitinning algorithm. \r\n\r\n 6.6.2 The sorting algorithm \r\n\r\n 6.6.3 Analysis of the quicksort algorithm \r\n\r\n 6.6.3.1 The worst case behavior \r\n\r\n 6.6.3.2 The average case behavior \r\n\r\n 6.6.4 Comparison of sorting algorithms \r\n\r\n 6.7 Multiplication of Large Integers \r\n\r\n 6.8 Matrin Multiplication \r\n\r\n 6.8.1 The traditional algorithm \r\n\r\n 6.8.2 Recursive version \r\n\r\n 6.8.3 Strassen's algorithm \r\n\r\n 6.8.4 Comparisons of the three algorithms \r\n\r\n 6.9 The Closest Pair Prob1em \r\n\r\n 6.9.1 Time complekity \r\n\r\n 6.10 Exercises \r\n\r\n 6.11 BibliograPhic Notes \r\n\r\n Chapter 7 Dynamic Programming \r\n\r\n 7.1 Introduction \r\n\r\n 7.2 The Longed Common Subsequence Problem \r\n\r\n 7.3 Matris Chain Multiplication \r\n\r\n 7.4 The Dynamic Programming Paradigm \r\n\r\n 7.5 The All-Pairs Shortest Path Problem. \r\n\r\n 7.6 The Knapsack Problem \r\n\r\n 7.7 Exercises \r\n\r\n 7.8 Bibliographic Notes \r\n\r\n PART 3 First-Cut Techniques \r\n\r\n Chapter 8 The Greedy Approach \r\n\r\n 8.1 Introduction \r\n\r\n 8.2 The Shortest Path Problem \r\n\r\n 8.2.1 A linear time algorithm for dense graphs \r\n\r\n 8.3 Minimum Cost Spanning nees (Kruskal's Algorithm) \r\n\r\n 8.4 Minimum Cost Spanning nees (Prim's Algorithm) \r\n\r\n 8.4.1 A linear time algorithm for dense graphs \r\n\r\n 8.5 File Compression \r\n\r\n 8.6 Exercises \r\n\r\n 8.7 Bibliographic Notes \r\n\r\n Chapter 9 Graph Thaversal \r\n\r\n 9.1 Introduction \r\n\r\n 9.2 Depth-First Search \r\n\r\n 9.2.1 Time'complexity of depth-first search \r\n\r\n 9.3 Applications of Depth-First Search \r\n\r\n 9.3.1 Graph acyclicity \r\n\r\n 9.3.2 Topological sorting \r\n\r\n 9.3.3 Finding articulation points in a graph \r\n\r\n 9.3.4 Strongly connected components \r\n\r\n 9.4 Breadth-First Search \r\n\r\n 9.5 Applications of Breadth-First Sparch \r\n\r\n \r\n\r\n \r\n\r\n 9.6 Exercises \r\n\r\n 9.7 Bibliographic Notes \r\n\r\n PART 4 Complexity of Problems \r\n\r\n Chapter 10 NP-Complete Problems \r\n\r\n 10.l Illtroduction \r\n\r\n 10.2 The Class P \r\n\r\n 10.3 The Class NP \r\n\r\n 10.4 NP-Complete Problems \r\n\r\n 10.4.1 The satisfiability problem \r\n\r\n 10.4.2 Vertex cover, independent set and clique problems \r\n\r\n 10.4.3 More NP-complete Problems \r\n\r\n 10.5 The Class co-NP \r\n\r\n 10.6 The Class NPI \r\n\r\n 10.7 The Relationips Between the Four Classes \r\n\r\n l0.8 Exercises \r\n\r\n 10.9 Biblioaraphic Notes \r\n\r\n Chapter 11 Introduction to Computational Complexity \r\n\r\n 11.1 Introduction \r\n\r\n 11.2 Mode of Computation: Tlie Turing Machine \r\n\r\n 11.3 k-tape Thring Machines and Time complexity \r\n\r\n 11.4 Off-Line Turing Machines and Space Complexity \r\n\r\n 11.5 Tape Compression and Linear Speed-Up \r\n\r\n 11.6 Relationships Between complexity Classes \r\n\r\n l1.6.1 Space and for hieraxchy theorems. \r\n\r\n 11.6.2 Padding arguments \r\n\r\n ll.7 Reductions \r\n\r\n 11.8 Completeness \r\n\r\n 1l.8.1 NLOGSPACE-complete problems \r\n\r\n 11.8.2 PSPACE-complete problems \r\n\r\n 11.8.3 P-complete problems \r\n\r\n 11.8.4 Some conclusions of completeness \r\n\r\n 11.9 The Polynomial Time Hierarchy \r\n\r\n 11.10 Exercises \r\n\r\n 11.11 Bibliographic Notes \r\n\r\n Chapter 12 Lower Bouuds \r\n\r\n 12.1 Introduction \r\n\r\n 12.2 Trivial Lower Bounds \r\n\r\n 12.3 The Decision Tree Model \r\n\r\n 12.3.1 The search problem \r\n\r\n 12.3.2 The sorting problem \r\n\r\n l2.4 The Algebraic Decision Tree Model \r\n\r\n l2.4.1 The element uniqueness problem \r\n\r\n 12.5 Linear Time bouctions \r\n\r\n 12.5.1 The convex hull problem \r\n\r\n 12.5.2 The closest pair problem \r\n\r\n 12.5.3 The Euclidean minimum spanning tree problem \r\n\r\n 12.6 Exercises \r\n\r\n 12.7 Bibliographic Notes \r\n\r\n PART 5 Coping with Hardness \r\n\r\n Chapter 13 Backtracking \r\n\r\n 13.1 Introduction \r\n\r\n 13.2 The 3-Coloring Problem \r\n\r\n 13.3 The 8-Queens Problem \r\n\r\n 13.4 The General Backtracking Method \r\n\r\n 13.5 Branch and Bound \r\n\r\n 13.6 Exercises \r\n\r\n 13.7 Bib1iographic notes \r\n\r\n Chapter 14 Randomized Algorithms \r\n\r\n 14.l Introduction \r\n\r\n 14.2 Las Vegas and Moote Carlo Algorithms \r\n\r\n 14.3 Randomised Quicksort \r\n\r\n l4.4 Randomized Selection \r\n\r\n l4.5 Testing String Equality \r\n\r\n 14.6 Pattern Matching \r\n\r\n 14.7 Random Sampling \r\n\r\n l4.8 Primality Testing \r\n\r\n 14.9 Exercises \r\n\r\n 14.10 Bibliographic Notes \r\n\r\n \r\n\r\n \r\n\r\n Chapter 15 Approximation Algorithms \r\n\r\n 15.1 Introduction \r\n\r\n 15.2 Basic Definitions \r\n\r\n l5.3 Difference Bounds \r\n\r\n 15.3.1 Planar graph coloring \r\n\r\n 15.3.2 Hardness result: the knapsack problem \r\n\r\n 15.4 Relative Performance Bounds \r\n\r\n 15.4.1 The bin packing problem \r\n\r\n 15.4.2 The Euclidean traveling salesman problem \r\n\r\n l5.4.3 The vertex cover problem \r\n\r\n 15.4.4 Hardness resu1t: the traveling sa1esman problem \r\n\r\n 15.5 Polynomial Approximation Schemes \r\n\r\n 15.5.1 The knapsack problem \r\n\r\n 15.6 Fully Po1ynomial Approximation Schemes \r\n\r\n 15.6.1 The subset-sum problem \r\n\r\n 15.7 Exercises \r\n\r\n 15.8 BibliograPhic NOtes \r\n\r\n PART 6 Iterative Improvement for Domain-Specific \r\n\r\n Problems \r\n\r\n Chapter 16 Network Flow \r\n\r\n 16.1 Introduction \r\n\r\n 16.2 Pre1iminaries \r\n\r\n 16.3 The Ford-Fulkerson Method \r\n\r\n 16.4 Mtalmum Capacity Augmelltation \r\n\r\n 16.5 Shortest Path Augmentation \r\n\r\n 16.6 Dinic's Algorithm \r\n\r\n 16.7 The MPM Algorithm \r\n\r\n 16.8 Exercises \r\n\r\n 16.9 Bibliographic Notes \r\n\r\n Chapter 17 Matching \r\n\r\n 17.1 Introduction \r\n\r\n l7.2 Preliminaries \r\n\r\n 17.3 Tbe Network Flow Method \r\n\r\n 17.4 The Hungarian Tree Method for Bipartite Graphs \r\n\r\n 17.5 Maximum Matching in General Graphs \r\n\r\n 17.6 An O(n) Algorithm for Bipwtite Graphs \r\n\r\n 17.7 Exercises \r\n\r\n 17.8 Bibllogranfor Notes \r\n\r\n PART 7 Techniques in Computational Geometry \r\n\r\n Chapter 18 Geometric Sweeping \r\n\r\n 18.1 Introduction \r\n\r\n 18.2 Geometric Preliminaries \r\n\r\n l8.3 Computing the Intersections of Line Segments \r\n\r\n 18.4 The Convex Hull Problem \r\n\r\n 18.5 Computing the Diameter of a Set of Points \r\n\r\n 18.6 Exercises \r\n\r\n 18.7 Bib1iographic Notes \r\n\r\n Chapter 19 Voronoi Diagrams \r\n\r\n l9.1 Introduction \r\n\r\n 19.2 Nearest-Point Voronoi Diagram \r\n\r\n 19.2.1 Delaunay triangulation \r\n\r\n 19.2.2 Construction of the Voronoi diagram \r\n\r\n l9.3 Applications of the Voronoi Diagram \r\n\r\n 19.3.1 Computing the convex hull \r\n\r\n 19.3.2 All nearest neighbors \r\n\r\n 19.3.3 The Euclidean minimum spanning tree \r\n\r\n 19.4 Farthed-Point Voronoi Diagram \r\n\r\n 19.4.1 Construction of the farthest-point Voronoi diagram \r\n\r\n 19.5 Applications of the Farthest-Point Voronoi Diagram \r\n\r\n 19.5.1 All farthest neighbors \r\n\r\n 19.5.2 Smallest enclosing circle \r\n\r\n 19.6 Exercises \r\n\r\n l9.7 Bibliographic Notes \r\n\r\n Bibliography \r\n\r\n Index \r\n
\r\n

多年来, 我一直想录找一本适合中国计算机系学生用的算法方面的国外教材. 尽管有些不错的国外教材在中国出版, 但总有篇幅过多. 内容略显陈旧或数据结构内容夹杂其中等等这样或那样的不甚满意之处.

去年我有幸看到世界科学图书出版社出版的由M. H. Alsuwaiyel撰写的《Algorithms Design Techniques and Analysis》, 它是以国际著名算法专家, 我国台湾出身的李德财教授所主编的系列丛书——Lecture Notes Series on Computing——中的一本. 虽然此书不是美国的大学教材, 而是沙特阿拉伯的大学计算机系教材. 但是我很快就被该书的组织简明. 概括, 且包含当前市面上算法一＃较少涉及的概率算法和近似算法的基本内容所吸引. 它是一本适合本科生学习算法的好书.

该书涉及数据结构的部分较少, 即使有一些, 表述上也很快与算法中比较复杂的集合查找和合并运算等相结合, 使读者不会感到和已经学过的数据结构相重复. 这比较适合中国大学计算机系中数据结构和算法分成两门开设的实际状况.

对于想了解NP完全问题基本概念的读者, 本书的篇幅给了他们基本的但又清楚的描绘. 本书还包括计算几何一章, 其取材也是适中的.

概. 4算法和近似算法是近20年算法研究迅猛发展的领域, 本书给予了足够的重视. 这也是本书特色之一, 是我向中国学生特别推荐的主要原因.

本书的另一个特色是以算法的设计技术为纲, 讲述一个又一个的算法技术, 然后分析其算法复杂性.

我希望本书的出版能满足短期内暂时无合适中文算法教材的空白. 诚挚地推荐给中国的广大算法老师采用本书作为教材.



朱洪

2002年10月1日

复旦大学



The fie1d of computer algorithms has flourished since the early l960's when the first users of electronic computers started to pay attention to the performance of programs. The Iimited resources of computers at that time resulted in additional impetus for devising efficient computer algorithms. After extensive research in this field, numerous efficient algorithms for different prob1ems emerged. The similarities among different algorithms for certain classes of problems have resuIted in general algorithm design techniques. This book emphasizes most of these algorithm design techniques that have proved their utility in the solution to many problems. It may be considered as an attempt to cover the most common techniques in the design of sequential algorithms. Each technique is presented as follows.

First, the context in which that technique can be app1ied. Second, the special characteristics of that technique that set it apart. Third, comparison with other techniques, whenever -possible; finally and most importantly illustration of the technique by applying it to severa1 problems.

Although the main theme of the book is algorithm design techniques,

it also emphasizes the other major component in algorithmic design: the analysis of algorithms. It covers in detail the analysis of most of the algorithms presented. Chapter 2 covers most of the mathematicaI tools that are helpful in analyzing algorithms. Chapter 11 is an introduction to the field of computational complexity and Chapter 12 covers the basics of establishing lower bounds on the solution of various problems. These chapters are indispensable for the design of efficient algorithms.

The focus of the presentation is on practical applications of the design techniques. Each technique is illustrated by providing an adequate number of algorithms to solve some problems that quite often arise in many applications in science and engineering.

The style of presentation of algorithms is straightforward, and uses pseudocode that is similar to the syntax of structured programming languages, e.g. if then-else, for and while constructs. The pseudooode is sometimes intermined with English whenever necessary Describing a portion of an algorithm in English is indeed instructive; it conveys the idea with minimum effort on the part of the reader. Howevr, sometimes it is both easier and more formal to use a pseudocode statement. For example, the function of the assignment statement B[1..n] - A[l..n]

is to replace each entry B[i] with A[i] for all i, 1 S i S n. Neither the for... end for construct nor plain English is more concise or easier to stste than this notation.

The book is divided into seven parts. Each part consists of chapters that cover those design techniques that have common characteristics or objectives. Part 1 sets the stage for the rest of the book, in addition to providing the background material that is needed in subsequent chapters.

Part 2 is devoted to the study of recursive design techniques, which are extremely important, as they emphasize a fundameotal tool in the field of computer science: recursion. Part 3 covers two intuitive and natural design techniques: the greedy approach and graph traversals. Part 4 is concerned with those techniques needed to investigate a given problem and the possibility of either coming up with an efficient algorithm for that problem, or proving its intrartability. This part covers NP-completeness, computa tional complexity and lower bounds. In Part 5, techniques for coping with hard problems are presented. These include backtracking, randomization

and finding approximate solutions that are reasonable and acceptable using a reasonable amount of time= Part 6 introduces the concept of iterative improvement using two important problems that have received extensive attention, which resulted in increasingly efficient algorithms: the problem of finding a maximum flow in a network and the problem of finding a maximum matching in an undirected graph. Finally Part 7 is an introduction to the relatively new field of computational geometry. In one chapter, the widely used technique of geometric sweeping is presented with examples of important problems in that field. In the other chapter, the versatile tool of the Voronoi diagram is covered, and some of its applications are presented.

The book is intended as a text in the field of the design and analysis of algorithms. It includes adequate material for two courses in algorithms.

Chapters 1 through 10 provide the core material fOr an undergraduate course in algorithms at the junior or senior leyel. Some of the material may be skipped such as the amortized analysis of the union-find algorithms, and the linear time algorithms in the case of dense graphs for the shortest path and minimum spanning tree problems. The instructor may find it useful to add some of the material in the following chapters such as backtracking, randomized algorithms, approximation a1gorithms or geometric sweeping.

The rest of the material is intended for a graduate course in algorithms.

The prerequisites for this book have been kept to the minimum; only an elementary background in discrete mathematics and data structures are assumed.

The author is grateful to King Fahd University of Petroleum & Minerals (KFUPM) for their support and providing farilities for the preparation of the manuscript. This book writing project has been funded by KFUPM under Project ics/algorithm/182. The Author would like to thank those

who have critically read various portions of the manuscript and offered many helpful suggeStions, including the students of the undergraduate and graduate Algorithms courses at KFUPM. Special thanks go to S. Albassam, H. Almuallim, and S. Ghanta for their va1uable comments.

Dhahran, Saudi Arabia M. H. Alsuwaiyel