Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 计算机算法——设计与分析导论（第三版影印版）
发信站: 哈工大紫丁香 (2002年11月09日14:28:34 星期六), 站内信件

计算机算法——设计与分析导论（第三版影印版） ISBN 7-04-010048-7/TP.700　　P7
08
　　Computer Algorithms : Introduction to Design and Analysis (Third Edition
)
　　Sara Baase，Allen Van Gelder，2001.6出版，定价39.50元
　　本书的主要内容包括三部分，一是介绍了如何用算法解决在计算机应用中经常出现
的现实问题，二是介绍了计算复杂性的基本原理与技术，最后讲解了NP-完备性问题及并
行算法。本书强调算法设计技术，对每一个问题，首先讨论多个解决方法，然后设计、
分析、修改或放弃某一算法，通过不断的深入研究，直到最后得到满意的结果。因此本
书作者希望读者阅读此书，逐步培养形成一种新的分析问题的思维方式。
　　本书在第二版的基础上，增加了三章新内容以及许多新的主题，同时对原有章节也
做了重新调整。本版次还新增了100多道习题和Java实例，书中的所有程序均以Java伪码
形式给出。
　　内容：1. 算法分析原理2. 数据抽象与基本数据结构3. 递归与归纳4. 分类5. 选择
6. 动态集合与查找7. 图与图的遍历8. 图的优化问题与贪心算法9. 传递闭包10. 动态
编程11. 字符串匹配12. 多项式与矩阵13. NP-完备性问题14. 并行算法附录 Java实例
与技术
Preface
Purpose
　　This book is intended for an upper-division or graduate course in algori
thms. It has sufficient material to allow several choices of topics.
　　The purpose of the book is threefold. It is intended to teach algorithms
 for solving real problems that arise frequently in computer applications, t
o teach basic principles and techniques of computational complexity (worst-c
ase and average behavior. space usage, and lower bounds on the complexity of
 a problem), and to introduce the areas of NP completeness and parallel algo
rithms.
　　Another of the book's aims, which is at least as important as teaching t
he subject matter, is to develop in the reader the habit of always respondin
g to a new algorithm with the questions: How good is it? Is there a better w
ay? Therefore, instead of presenting a series of complete, "pulled-out-of-a-
hat" algorithms with analysis, the text often discusses a problem first, con
siders one or more approaches to solving it (as a reader who sees the proble
m for the first time might), and then begins to develop an algorithm, analyz
es it, and modifies or rejects it until a satisfactory result is produced. (
Alternative approaches that are ultimately rejected are also considered in t
he exercises; it is useful for the reader to know why they were rejected.)
　　Questions such as: How can this be done more efficiently? What data stru
cture would be useful here? Which operations should we focus on to analyze t
his algorithm? How must this variable (or data structure) be initialized? Ap
pear frequently throughout the text. Answers generally follow the questions,
 but we suggest readers pause before reading the ensuing text and think up t
heir own answers. Learning is not a passive process.
　　We hope readers will also learn to be aware of how an algorithm actually
 behaves on various inputs-hat is, which branches are followed? What is the 
pattern of growth and shrinkage of stacks? How does presenting the input in 
different ways (e.g., listing the vertices or edges of a graph in a differen
t order) affect the behavior? Such questions are raised in some of the exerc
ises, but are not emphasized in the text because they require carefully goin
g through the details of many examples.
　　Most of the algorithms presented are of practical use; we have chosen no
t to emphasize those with good asymptotic behavior that are poor for inputs 
of useful sizes (though some important ones are included). Specific algorith
ms were chosen for a variety of reasons including the importance of the prob
lem, illustrating analysis techniques, illustrating techniques (e.g., depth-
first search) that give rise to numerous algorithms, and illustrating the de
velopment and improvement of techniques and algorithms (e.g., Union-Find pro
grams).
Prerequisites
　　The book assumes familiarity with data structures such as linked lists, 
stacks, and trees, and prior exposure to recursion. However, we include a re
view, with specifications, for the standard data structures and some special
ized ones. We have also added a student-friendly review of recursion.
　　Analysis of algorithms uses simple properties of logarithms and some cal
culus (differentiation to determine the asymptotic order of a function and i
ntegration to approximate summations), though virtually no calculus is used 
beyond Chapter 4. We find many students intimidated when they see the first 
log or integral sign because a year or more has passed since they had a calc
ulus course. Readers will need only a few properties of logs and a few integ
rals from first-semester calculus. Section I .3 reviews some of the necessar
y mathematics, and Section 1.5.4 provides a practical guide.
Algorithm Design Techniques
　　Several important algorithm design techniques reappear in 1llany algorit
hms. These include divide-and-conquer, greedy methods, depth-first search (f
or graphs), and dynamic programming. This edition puts more emphasis on algo
rithm design techniques than did the second edition. Dynamic programming, as
 before, has its own chapter and depth-first search is presented with many a
pplications in the chapter on graph traversals (Chapter 7). Most chapters ar
e organized by application area, rather than by design technique, so we prov
ide here a list of places where you will find algorithms using divide-and-co
nquer and greedy techniques.
　　The divide-and-conquer technique is described in Section 4.3. It is used
 in Binary Search (Section 1 .6), most sorting methods (Chapter 4), median f
inding and the general selection problem (Section 5.4), binary search trees 
(Section 6.4), polynomial evaluation (Section 12.2), matrix multiplication (
Section 12.3), the Fast Fourier Transform (Section 12.4), approximate graph 
coloring (Section 13.7), and, in a slightly different form, for parallel com
putation in Section 14.5.
　　Greedy algorithms are used for finding minimum spanning trees and shorte
st paths in Chapter 8, and for various approximation algorithms for ac-hard 
optimization problems, such as bin packing, knapsack, graph coloring, and tr
aveling salesperson (Sections 13.4 through 13.8).
Changes from the Second Edition
　　This edition has three new chapters and many new topics. Throughout the 
book, numerous sections have been extensively rewritten. A few topics from t
he second edition have been moved to different chapters where we think they 
fit better. We added more than 100 new exercises, many bibliographic entries
, and an appendix with Java examples. Chapters 2, 3, and 6 are virtually all
 new.
　　Chapter 2 reviews abstract data types (ADTs) and includes specifications
 for several standard ADTs. The role of abstract data types in algorithm des
ign is emphasized throughout the book.
　　Chapter 3 reviews recursion and induction, emphasizing the connection be
tween the two and their usefulness in designing and proving correctness of p
rograms. The chapter also develops recursion trees, which provide a visual a
nd intuitive representation of recurrence equations that arise in the analys
is of recursive algorithms. Solutions for commonly occurring patterns are su
mmarized so they are available for use in later chapters.
　　Chapter 6 covers hashing, red-black trees for balanced binary trees, adv
anced priority queues, and dynamic equivalence relations (Union-Find). The l
atter topic was moved from different chapter in the second edition.
　　We rewrote all algorithms in a Java-based pseudocode. Familiarity with J
ava is not required; the algorithms can be read easily by anyone familiar wi
th C or C++. Chapter I has an introduction to the Java-based pseudocode.
　　We significantly expanded the section on mathematical tools for algorith
m analysis in Chapter I to provide a better review and reference for same of
 the mathematics used in the book. The discussion of the asymptotic order of
 functions ill Section 1.5 was designed to help students gain a better maste
ry of the concepts and techniques for dealing with asymptotic order. We adde
d rules, informal language, that summarize the most common cases (Section 1.
5.4).
　　Chapter 4 contains an accelerated version of Heapsort in which the numbe
r of key comparisons is cut nearly in half. For Quicksort, we use the Hoare 
partition algorithm in the main text. Lomuto's method is introduced in an ex
ercise. (This is reversed from the second edition.)
　　We split the old graph chapter into two chapters, and changed the order 
of some topics. Chapter 7 concentrates on (linear time) traversal algorithms
. The presentation of depth-first search has been thoroughly revised to emph
asize the general structure of the technique and show more applications. We 
added topological sorting and critical path analysis as applications and bec
ause of their intrinsic value and their connection to dynamic programming. S
harir's algorithm, rather than Tarjan's, is presented for strongly connected
 components.
　　Chapter & covers greedy algorithms for graph problems. The presentations
 of the Prim algorithm for minimum spanning trees and the Dijkstra algorithm
 for shortest paths were rewritten to emphasize the roles of priority queues
 and to illustrate how the use of abstract data types can lead the designer 
to efficient implementations. The asymptotically optimal Θ(m+nlogn) impleme
ntation is mentioned, but is not covered in depth. We moved Kruskal's algori
thm for minimum spanning trees to this chapter
　　The presentation of dynamic programming (Chapter 10) was substantially r
evised to emphasize a general approach to finding dynamic programming soluti
ons. We added a new application, a text-formatting problem, to reinforce the
 point that not all applications call for a two-dimensional array. We moved 
the approximate string matching application (which was in this chapter in th
e second edition) to the string matching chapter (Section I l.5). The exerci
ses include some other new applications.
　　Our teaching experience has pinpointed particular areas where students h
ad difficulties with concepts related to P and NP (Chapter 13), particularly
 nondeterministic algorithms and polynomial transformations. We rewrote some
 definitions and examples to make the concepts cleared. We added a short sec
tion on approximation algorithms for the traveling salesperson problem and a
 section on DNA computing.
　　Instructors who used the second edition may particularly want to note th
at we changed some conventions and terminology (usually to conform to common
 usage). Array indexes now often begin at 0 instead of 1. (In some cases, wh
ere numbering from I was clearer, we left it that way.) We now use the term 
depth rather than level for the depth of a node in a tree. We use height ins
tead of depth for the maximum depth of any node in a tree. In the second edi
tion, a path in a graph was defined to be what is commonly called a simple p
ath; we use the more general definition for path in this edition and define 
simple path separately. A directed graph may now contain a self-edge.
Exercises and Programs
　　Some exercises are somewhat open-ended. For example, one might ask for a
 good lower bound for the complexity of a problem, rather than asking studen
ts to show that a given function is a lower bound. We did this for two reaso
ns. One is to make the form of the question more realistic; a solution must 
be discovered as well as verified. The other is that it may be hard for some
 students to prove the best known lower bound (or find the most efficient al
gorithm for a problem), but there is still a rang" of solutions they can off
er to show their mastery of the techniques studied.
　　Some topics and interesting problems are introduced only in exercises. F
or example, the maximum independent set problem for a tree is an exercise in
 Chapter 3, the maximum subsequence sum problem is an exercise in Chapter 4,
 and the sink finding problem for a graph is an exercise in Chapter 7. Sever
al NP-complete problems are introduced in exercises in Chapter 13.
　　The abilities, background, and mathematical sophistication of students a
t different universities vary considerably, making it difficult to decide ex
actly which exercises should be marked ("started") as "hard." We starred exe
rcises that use more than minimal mathematics, require substantial creativit
y, or require a long chain of reasoning. A few exercises have two stars. Som
e starred exercises have hints.
　　The algorithms presented in this book are not programs; that is, many de
tails not important to the method or the analysis are omitted. Of course, st
udents should know how to implement efficient algorithms in efficient, debug
ged programs. Many instructors may teach this course as a pure "theory" cour
se without programming. For those who want to assign programming projects, m
ost chapters include a list of programming assignments. These are brief sugg
estions that may need amplification by Instructors who choose to use them.
Selecting Topics for Your Course
Clearly the amount of material and the particular selection of' topics to co
ver depend on the particular course and student population. We present sampl
e outlines for two undergraduate courses and one graduate course.
　　This outline corresponds approximately to the senior-level course Sara B
aase teaches at San Diego State University in a 15-week semester with 3 hour
s per week of lecture.
　　Chapter l: The whole chapter is assigned as reading but I concentrate on
 Sections 1.4 and 1.5 in class.
　　Chapter 2：Sections 2.1 through 2.4 assigned as reading.
　　Chapter 3: Sections 3.1 through 3.4, 3.6, and 3.7 assigned as reading wi
th light coverage in class.
　　Chapter 4: Sections 4.1 through 4.9.
　　Chapter 5: Sections 5.1 through 5.2, 5.6, and some of 5.4.
　　Chapter 7: Sections 7.1 through 7.4 and either 7.5 or 7.6 and 7.7.
　　Chapter 8: Sections 8.1 through 8.3 and brief mention of 8.4.
　　Chapter 11: Sections 11.1 through 11.4.
　　Chapter 13: Sections 13.1 through 13.5, 13.8, and 13.9.
　　The next outline is the junior-level course Alien Van Gelder teaches at 
the University of California, Santa Cruz, in a 10-week quarter with 3.5 hour
s per week of lecture.
　　Chapter 1: Sections 1.3 and 1.5, and remaining sections as reading.
　　Chapter 2: Sections 2.1 through 2.3, and remaining sections as reading.
　　Chapter 3: All sections are touched on; a lot is left for reading.
　　Chapter 4: Sections 4.1 through 4.9.
　　Chapter 5: Possibly Section 5.4, the average linear time algorithm only.

　　Chapter 6: Sections 6.4 through 6.6.
　　Chapter 7: Sections 7.1 through 7.6.
　　Chapter 8: The entire chapter.
　　Chapter 9: Sections 9.1 through 9.4.
　　Chapter 10: Possibly Sections 10.1 through 10.3, but usually no time.
　　For the first-year graduate course at the University of California, Sant
a Cruz (also 10 weeks, 3.5 hours of lecture), the above material is compress
ed and the following additional topics are covered.
　　Chapter 5: The entire chapter
　　Chapter 6: The remainder of the chapter, with emphasis on amortized anal
ysis.
　　Chapter 10: The entire chapter.
　　Chapter 13: Sections 13.1 through 13.3, and possibly Section 13.9.
　　The primary dependencies among chapters are shown in the following diagr
am with solid lines; some secondary dependencies are indicated with dashed l
ines. A secondary dependency means that only a few topics in the earlier cha
pter are needed in the later chapter, or that only the more advanced section
s of the later chapter require the earlier one.
   While material in Chapters 2 and 6 is important to have seen, a lot of it
 might have been covered in an earlier course. Some sections in Chapter 6 ar
e important for the more advanced parts of Chapter 8.
　　We like to remind readers of common themes or techniques, so we often re
fer back to earlier sections; many of these references can be ignored if the
 earlier sections were not covered. Several chapters have a section on lower
 bounds, which benefits from the ideas and examples in Chapter 5, but the di
agram does not show that dependency because many instructors do not cover lo
wer bounds.
　　We marked ("starred") sections that contain more complicated mathematics
 or more complex or sophisticated arguments than most others, but only where
 the material in not central to the book. We also starred one or two section
s that contain optional digressions. We have not starred a few sections that
 we consider essential to a course for which the book is used, even though t
hey contain a lot of mathematics. For example, at least some of the material
 in Section l.5 on the asymptotic growth rate of functions and in Section 3.
7 on solutions of recurrence equations should be covered.
Acknowledgments
　　We are happy to take this opportunity to thank the people who helped in 
big and small ways in the preparation of the third edition of this book.
　　Sara Baase acknowledges the influence and inspiration of Dick Karp, who 
made the subject of computational complexity exciting and beautiful in his s
uperb lectures. Alien Van Gelder acknowledges the insights gained from Bob F
loyd, Don Knuth, Ernst Maye, Vaughan Pratt, and Jeff Ullman; they all teach 
more than is "in the book.” Alien also wishes to acknowledge colleagues Dav
id Helmbold for many discussions on how to present algorithms effectively an
d on fine points of many algorithms, and Charlie McDowell for help on many o
f the aspects of Java that are covered in tills book's appendix. We thank Li
la Kari for reading an early draft of the section on DNA computing and answe
ring our questions.
　　 Of course, we’d have nothing to write about without the many people wh
o did the original research that provided the material we enjoy learning and
 passing on to new generations of students. We thank them for their work.
　　In the years since the second edition appeared, several students and ins
tructors who used the book sent in lists of errors, typos, and suggestions f
or changes. We don't have a complete list of names, but we appreciate the ti
me and thought that went into their letters.
　　The surveys and manuscript reviews obtained by Addison-Wesley were espec
ially helpful. Our thanks to Iliana Bjorling-Sachs (Lafayette College), Moha
mmad B. Dadfar (Bowling Green State University), Daniel Hirschberg (Universi
ty of California at lrvine), Mitsunori Ogihara (University of Rochester), R.
 W. Robinson (University of Georgia), Yaakov L. Varol (University of Nevada,
 Reno), William W. White (Southern Illinois University at Edwardsville), Daw
n Wilkins (University of Mississippi), and Abdou Youssef(George Washington U
niversity).
　　We thank our editors at Addison-Wesley, Matte Suarez-Rivas and Karen Wer
nholm, for their confidence and patience in working with us on this project 
that of tell departed from standard production procedures and schedules. We 
thank Joan Flaherty for her painstakingly careful copy editing and valuable 
suggestions for improving the presentation. Brooke Albright's careful proofr
eading detected many errors that had survived earlier scrutiny; of course, a
ny that remain are the fault of the authors.
　　We thank Keith Mayers for assisting us in various ways. Sara thanks him 
for not reminding her too often that she broke her wedding vow to work less 
than seven days a week.
Sara Baase, San Diego, California
http://www-rohan.sdsu.edu/faculy/baase
Alien Van Gelder, Santa Crux, California
http: //www.cse.ucsc.edu/personnel/faculty/avg.html
June, 1999
Contents
Preface vii
1 Analyzing Algorithms and Problems: Principles and Examples 1
1.1 Introduction 2
1.2 Java as an Algorithm Language 3
1.3 Mathematical Background 11
1.4 Analyzing Algorithms and Problems 30
1.5 Classifying Functions by Their Asymptotic Growth Rates 43
1.6 Searching an Ordered Array 53
　　Exercises 61
　　Notes and References 67
2 Data Abstraction and Basic Data Structures 69
2.1 Introduction 70
2.2 ADT Specification and Design Techniques 71
2.3 Elementary ADTs--Lists and Trees 73
2.4 Stacks and Queues 86
2.5 ADTs for Dynamic Sets 89
　　Exercises 95
　　Notes and References 100
3 Recursion and induction 101
3.1 introduction 102
3.2 Recursive Procedures 102
3.3 What is a Proof? 108
3.4 Induction Proofs 111
3.5 Proving Correctness of Procedures 1 18
3.6 Recurrence Equations 130
3.7 Recursion Trees 134
　　Exercises 141
　　Notes and References 146
4 Sorting 149
4.1 Introduction 150
4.2 Insertion Sort 151
4.3 Divide and Conquer 157
4.4 Quicksort 159
4.5 Merging Sorted Sequences 171
4.6 Mergesort 174
4.7 Lower Bounds for Sorting by Comparison of Keys 178
4.8 Heapsort 182
4.9 Comparison of Four Sorting Algorithms 197
4.10 Shellsort 197
4.11 Radix Sorting 201
　　Exercises 206
　　Programs 221
　　Notes and References 221
5 Selection and Adversary Arguments 223
5.1 Introduction 224
5.2 Finding max and min 226
5.3 Finding the Second-Largest Key 229
5.4 The Selection Problem 233
5.5 A Lower Bound for Finding the Median 238
5.6 Designing Against an Adversary 240
　　Exercises 242
　　Notes and References 246
6 Dynamic Sets and Searching 249
6.1 Introduction 250
6.2 Array Doubling 250
6.3 Amortized Time Analysis 251
6.4 Red-Black Trees 253
6.5 Hashing 275
6.6 Dynamic Equivalence Relations and Union-Find Programs 283
6.7 Priority Queues with a Decrease Key Operation 295
　　Exercises 302
　　Programs 309
　　Notes and References 309
7 Graphs and Graph Traversals 313
7.1 Introduction 314
7.2 Definitions and Representations 314
7.3 Traversing Graphs 328
7.4 Depth-First Search on Directed Graphs 336
7.5 Strongly Connected Components of a Directed Graph 357
7.6 Depth-First Search on Undirected Graphs 364
7.7 Biconnected Components of an Undirected Graph 366
　　Exercises 375
　　Programs 384
　　Notes and References 385
8 Graph Optimization Problems and Greedy Algorithms 387
8.1 Introduction 388
8.2 Prim's Minimum Spanning Tree Algorithm 388
8.3 Single-Source Shortest Paths 403
8.4 Kruskal's Minimum Spanning Tree Algorithm 412
　　Exercises 416
　　Programs 421
　　Notes and References 422
9 Transitive Closure, All-Pairs Shortest Paths 425
9.1 Introduction 426
9.2 The Transitive Closure of a Binary Relation 426
9.3 Warshall's Algorithm for Transitive Closure 430
9.4 All-Pairs Shortest Paths in Graphs 433
9.5 Computing Transitive Closure by Matrix Operations 436
9.6 Multiplying Bit Matrices-Kronrod's Algorithm 439
　　Exercises 446
　　Programs 449
　　Notes and References 449
10 Dynamic Programming 451
10.1 Introduction 452
10.2 Subproblem Graphs and Their Traversal 453
10.3 Multiplying a Sequence of Matrices 457
10.4 Constructing Optimal Binary Search Trees 466
10.5 Separating Sequences of Words into Lines 471
10.6 Developing a Dynamic Programming Algorithm 474
　　Exercises 475
　　Programs 481
　　Notes and References 482
11 String Matching 483
11.1 Introduction 484
11.2 A Straightforward Solution 485
11.3 The Knuth-Moms-Pratt Algorithm 487
11.4 The Boyer-Moors Algorithm 495
11.5 Approximate String Matching 504
　　Exercises 508
　　Programs 512
　　Notes and References 512
12 Polynomials and Matrices 515
12.1 Introduction 516
12.2 Evaluating Polynomial Functions 516
12.3 Vector and Matrix Multiplication 522
12.4 The Fast Fourier Transform and Convolution 528
　　Exercises 542
　　Programs 546
　　Notes and References 546
13 NP-Complete Problems 547
13.1 Introduction 548
13.2 T and ac 548
13.3 NP-Complete Problems 559
13.4 Approximation Algorithms 570
13.5 Bin Packing 572
13.6 The Knapsack and Subset Sum Problems 577
13.7 Graph Coloring 581
13.8 The Traveling Salesperson Problem 589
13.9 Computing with DNA 592
　　Exercises 600
　　Notes and References 608
14 Parallel Algorithms 611
14.1 Introduction 612
14.2 Parallelism, the PRAM, and Other Models 612
14.3 Some Simple PRAM Algorithms 616
14.4 Handling Write Conflicts 622
14.5 Merging and Sorting 624
14.6 Finding Connected Components 628
14.7 A Lower Bound for Adding n Integers 641
　　Exercises 643
　　Notes and References 647
A Java Examples and Techniques 649
A.1 introduction 650
A.2 A Java Main Program 651
A.3 A Simple input Library 656
A.4 Documenting Java Classes 658
A.5 Generic Order and the "Comparable" Interface 659
A.6 Subclasses Extend the Capability of Their Superclass 663
A.7 Copy via the "Cloneable" Interface 667
Bibliography　　669
Index　　679

--
小猪很伤心地哭着。
妈妈问：哭什么？
小猪说：我觉得自已很笨。
妈妈安慰他：孩子，别哭，看这各签名档的人比你还笨呢！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.33.243]