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