前 言 20世纪末，以计算机和通信技术为代表的信息科学和技术，对世界的经济、军事 科技、教育、文化、卫生等方面的发展产生了深刻的影响，由此而兴起的信息产业已 经成为世界经济发展的支柱。进入21世纪，各国为了加快本国的信息产业，加大了资 金投入和政策扶持。 为了加快我国信息产业的进程，在我国《国民经济和社会发展第十个五年计划纲 要》中，明确提出“以信息化带动工业化，发挥后发优势，实现社会生产力的跨越式 发展。”信息产业的国际竞争将日趋激烈。在我国加入WT0后，我国信息产业将面临 国外竞争对手的严峻挑战。竟竞争成败最终将取决于信息科学和技术人才的多少与代 劣。 在20世纪末，我国信息产业虽然得到迅猛发展，但与国际先进国家相比，差距还 很大。为了赶上并超过国际先进水平，我国必须加快信息技术人才的培养，特别要培 养一大找具有国际竞争能力的高水平的信息技术人才，促进我国信息产业和国家信息 化水平的全面提高。为此，教育部高等教育司根据教育部吕福源副部长的意见，在长 期重视推动商等学校信息科学和技术教学的基础上，将实施超前发展战略，采取一些 重要举措，加快推动高等学校的信息科学和技术等相关专业的教学工作。在大力宣传、 推荐我国专家编著的面向21世纪和“九五”重点的信息科学和技术课程教材的基础 上，在有条件的高等学校的某些信息科学和技术课程中推动使年国外优秀教材的影印 版进行英语或效语教学，以缩短我国在计算机教学上与国际先进水平的差距，同时也 有助于强化我国大学生的英语水平。 为了达到上述目的，在分析一些出版社已影印相关教材，一些学校已试用影印教 材进行教学的基础上，教育部高等教育司组织并委托高等教育出版社开展国外优秀信 患科学和技术优秀教材及其教学辅助材料的引进研究与影印出版的试点工作。为推动 用彭印版教材进行教学创造条件。 本次引进的系列教材的影印出版工作，是在对我国高校信息科学和技术专业的课 程与美国高校的进行对比分析的基础上展开的；所影印出版的教材均由我国主要高校
的信息科学和技术专家组成的专家组，从国外近两年出版的大量最新教材中精心筛选 评审通过的内容新、有影响的优秀教材；影印教材的定价原则上应与我国大学教材价 格相当。 教育部高等教育司将此影印系列教材推荐给高等学校，希望有关教师选用，使用 后有什么意见和建议请及时反馈。也希望有条件的出版社，根据影印教材的要求，积 极参加此项工作，以便引进更多、更新、更好的外国教材和教学辅助材料。 同时，感谢国外有关出版公司对此项引进工作的配合，欢迎更多的国外公司关心 并参与此项工作。 教育部高等教育司 二00一年四月
Preface Purpose This book is intended for an upper-division or graduate course in algorithms.It has suffi- cient 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,to teach basic principles and techniques of computational complexity (worst-case and average behavior,space usage, and lower bounds on the complexity of a problem),and to introduce the areas of NP- completeness and parallel algorithms. Another of the book's aims,which is at least as important as teaching the subject matter,is to develop in the reader the habit of always responding to a new algorithm with the questions:How good is it?Is there a better way?Therefore,instead of presenting a series of complete,"pulled-out-of-a-hat"algorithms with analysis,the text often discusses a problem first,considers one or more approaches to solving it (as a reader who sees the problem for the first time might),and then begins to develop an algorithm,analyzes it,and modifies or rejects it until a satisfactory result is produced.(Altemnative approaches that are ultimately rejected are also considered in the 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 structure would be useful here?Which operations should we focus on to analyze this algorithm?How must this variable (or data structure)be initialized?appear frequently throughout the text. Answers generally follow the questions,but we suggest readers pause before reading the ensuing text and think up their own answers.Learning is not a passive process. We hope readers will also leam to be aware of how an algorithm actually behaves on various inputs-that 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 different order)affect the behavior?Such questions are raised in some of the exercises,but are not emphasized in the text because they require carefully going through the details of many examples. Most of the algorithms presented are of practical use;we have chosen not to empha- size those with good asymptotic behavior that are poor for inputs of useful sizes (though some important ones are included).Specific algorithms were chosen for a variety of reasons
viii Preface including the importance of the problem,illustrating analysis techniques,illustrating tech- niques (e.g.,depth-first search)that give rise to numerous algorithms,and illustrating the development and improvement of techniques and algorithms (e.g,Union-Find programs). Prerequisites The book assumes familiarity with data structures such as linked lists,stacks,and trees. and prior exposure to recursion.However,we include a review,with specifications,for the standard data structures and some specialized ones.We have also added a student-friendly review of recursion. Analysis of algorithms uses simple properties of logarithms and some calculus(dif- ferentiation to determine the asymptotic order of a function and integration to approximate summations),though virtually no calculus is used beyond Chapter 4.We find many stu- dents intimidated when they see the first log or integral sign because a year or more has passed since they had a calculus course.Readers will need only a few properties of logs and a few integrals from first-semester calculus.Section 1.3 reviews some of the necessary mathematics,and Section 1.5.4 provides a practical guide. Algorithm Design Techniques Several important algorithm design techniques reappear in many algorithms.These in- clude divide-and-conquer,greedy methods,depth-first search (for graphs),and dynamic programming.This edition puts more emphasis on algorithm design techniques than did the second edition.Dynamic programming,as before,has its own chapter and depth-first search is presented with many applications in the chapter on graph traversals(Chapter 7). Most chapters are organized by application area,rather than by design technique,so we provide here a list of places where you will find algorithms using divide-and-conquer and greedy techniques. The divide-and-conguer technique is described in Section 4.3.It is used in Binary Search (Section 1.6),most sorting methods(Chapter 4),median finding 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 (Sec- tion 12.4).approximate graph coloring (Section 13.7),and,in a slightly different form, for parallel computation in Section 14.5. Greedy algorithms are used for finding minimum spanning trees and shortest paths in Chapter 8,and for various approximation algorithms for NP-hard optimization problems, such as bin packing,knapsack,graph coloring,and traveling 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 the 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
Preface ix Chapter 2 reviews abstract data types (ADTs)and includes specifications for several standard ADTs.The role of abstract data types in algorithm design is emphasized through- out the book. Chapter 3 reviews recursion and induction,emphasizing the connection between the two and their usefulness in designing and proving correctness of programs.The chapter also develops recursion trees,which provide a visual and intuitive representation of recur- rence equations that arise in the analysis of recursive algorithms.Solutions for commonly occurring patterns are summarized so they are available for use in later chapters. Chapter 6 covers hashing,red-black trees for balanced binary trees,advanced priority queues,and dynamic equivalence relations (Union-Find).The latter topic was moved from a different chapter in the second edition. We rewrote alt algorithms in a Java-based pseudocode.Familiarity with Java is not required;the algorithms can be read easily by anyone familiar with C or C++.Chapter I has an introduction to the Java-based pseudocode. We significantly expanded the section on mathematical tools for algorithm analysis in Chapter I to provide a better review and reference for some of the mathematics used in the book.The discussion of the asymptotic order of functions in Section 1.5 was designed to help students gain a better mastery of the concepts and techniques for dealing with asymptotic order.We added rules,in informal language,that summarize the most common cases (Section 1.5.4). Chapter 4 contains an accelerated version of Heapsort in which the number 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 exercise.(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 emphasize the general structure of the technique and show more applications.We added topological sorting and critical path analysis as applications and because of their intrinsic value and their connection to dynamic programming.Sharir's algorithm,rather than Tarjan's,is presented for strongly connected components Chapter 8 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 icad the designer to efficient implementations.The asymptotically optimal (m +n log n)implementation is mentioned,but is not covered in depth.We moved Kruskal's algorithm for minimum spanning trees to this chapter. The presentation of dynamic programming (Chapter 10)was substantially revised to emphasize a general approach to finding dynamic programming solutions.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 the second edition)to the string matching chapter (Sec- tion 11.5).The exercises include some other new applications