xii Preface 14 10 1③ While material in Chapters 2 and 6 is important to have seen,a lot of it might have been covered in an earlier course.Some sections in Chapter 6 are important for the more advanced parts of Chapter 8. We like to remind readers of common themes or techniques,so we often refer back to earlier sections;many of these references can be ignored if the earlier sections were not covered.Several chapters have a section on lower bounds,which benefits from the ideas and examples in Chapter 5,but the diagram does not show that dependency because many instructors do not cover lower bounds. We marked ("starred")sections that contain more complicated mathematics or more complex or sophisticated arguments than most others,but only where the material is not central to the book.We also starred one or two sections that contain optional digressions. We have not starred a few sections that we consider essential to a course for which the book is used,even though they contain a lot of mathematics.For example,at least some of the material in Section 1.5 on the asymptotic growth rate of functions and in Section 3.7 on solutions of recurrence equations should be covered. Acknowledgments We are happy to take this opportunity to thank the people who helped in big and small ways in the preparation of the third edition of this book. Sara Baase acknowledges the influence and inspiration of Dick Karp,who made the subject of computational complexity exciting and beautiful in his superb lectures.Allen Van Gelder acknowledges the insights gained from Bob Floyd,Don Knuth,Ernst Mayr, Vaughan Pratt,and Jeff Ullman;they all teach more than is "in the book."Allen also wishes to acknowledge collcagucs David Helmbold for many discussions on how to present algorithms effectively and on fine points of many algorithms,and Charlie McDowell for help on many of the aspects of Java that are covered in this book's appendix.We thank Lila Kari for reading an early draft of the section on DNA computing and answering our questions. Of course,we'd have nothing to write about without the many people who did the original research that provided the material we enjoy learning and passing on to new generations of students.We thank them for their work. In the years since the second edition appeared,several students and instructors who used the book sent in lists of errors.typos,and suggestions for changes.We don't have a complete list of names,but we appreciate the time and thought that went into their letters. The surveys and manuscript revicws obtained by Addison-Wesley were especially helpful.Our thanks to lliana Bjorling-Sachs (Lafayeite College),Mohammad B.Dadfar (Bowling Green State University),Daniel Hirschberg (University of California at Irvine)