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