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