Preface Our teaching experience has pinpointed particular areas where students had 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 clearer.We added a short section 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 that 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,where 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 instead of depth for the maximum depth of any node in a tree.In the second edition,a path in a graph was defined to be what is commonly called a simple path;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 students to show that a given function is a lower bound.We did this for two reasons.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 algorithm for a problem),but there is still a range of solutions they can offer to show their mastery of the techniques studied. Some topics and interesting problems are introduced only in exercises.For 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.Several NP-complete problems are introduced in exercises in Chapter 13. The abilities,background,and mathematical sophistication of students at different uni- versities vary considerably,making it difficult to decide exactly which exercises should be marked("starred")as "hard."We starred exercises that use more than minimal mathemat- ics,require substantial creativity,or require a long chain of reasoning.A few exercises have two stars.Some starred exercises have hints. The algorithms presented in this book are not programs;that is,many details not important to the method or the analysis are omitted.Of course,students should know how to implement efficient algorithms in efficient,debugged programs.Many instructors may teach this course as a pure "theory"course without programming.For those who want to assign programming projects,most chapters include a list of programming assignments. These are brief suggestions 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 cover depend on the particular course and student population.We present sample outlines for two undergraduate courses and one graduate course