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
Preface xi This outline corresponds approximately to the senior-level course Sara Baase teaches at San Diego State University in a 15-week semester with 3 hours per week of lecture. Chapter 1:The whole chapter is assigned as reading but I concentrate on Sections 1.4 and 1.5 in class. Chapter 2:Sections 2.1 through 2.4 assigned as reading Chapter 3:Sections 3.1 through 3.4.3.6,and 3.7 assigned as reading with light cover- age in class. Chapter 4:Sections 4.1 through 4.9. Chapter 5:Sections 5.I through 5.2,5.6,and some of 5.4 Chapter 7:Sections 7.1 through 7.4 and either 7.5 or 7.6 and 7.7. Chapter 8:Sections 8.1 through 8.3 and brief mention of 8.4. Chapter 11:Sections 11.1 through 11.4. Chapter 13:Sections 13.1 through 13.5,13.8,and 13.9. The next outline is the junior-level course Allen Van Gelder teaches at the University of California,Santa Cruz,in a 10-week quarter with 3.5 hours per week of lecture. Chapter 1:Sections 1.3 and 1.5,and remaining sections as reading. Chapter 2:Sections 2.1 through 2.3,and remaining sections as reading Chapter 3:All sections are touched on;a lot is left for reading Chapter 4:Sections 4.1 through 4.9 Chapter 5:Possibly Section 5.4,the average linear time algorithm only. Chapter 6:Sections 6.4 through 6.6. Chapter 7:Sections 7.1 through 7.6. Chapter 8:The entire chapter. Chapter 9:Sections 9.1 through 9.4. Chapter 10:Possibly Sections 10.I through 10.3,but usually no time. For the first-year graduate course at the University of California,Santa Cruz(also 10 weeks,3.5 hours of lecture).the above material is compressed and the following additional topics are covered. Chapter 5:The entire chapter. Chapter 6:The remainder of the chapter,with emphasis on amortized analysis. Chapter 10:The entire chapter. Chapter 13:Sections 13.1 through 13.3,and possibly Section 13.9. The primary dependencies among chapters are shown in the following diagram with solid lines;some secondary dependencies are indicated with dashed lines.A secondary dependency means that only a few topics in the earlier chapter are needed in the later chapter,or that only the more advanced sections of the later chapter require the earlier one
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)
Preface xiii Mitsunori Ogihara(University of Rochester),R.W.Robinson(University of Georgia). Yaakov L.Varol (University of Nevada,Reno),William W.White(Southern Illinois Uni- versity at Edwardsville),Dawn Wilkins(University of Mississippi),and Abdou Youssef (George Washington University). We thank our editors at Addison-Wesley,Maite Suarez-Rivas and Karen Wernholm, for their confidence and patience in working with us on this projcct that often dcparted from standard production procedures and schedules.We thank Joan Flaherty for her painstak- ingly careful copy editing and valuable suggestions for improving the presentation.Brooke Albright's careful proofreading detected many errors that had survived earlier scrutiny;of course,any that remain are the fault of the authors. We thank Keith Mayers for assisting us in various ways.Sara thanks him for not reminding her too often that she broke her wedding vow to work less than seven days a week. Sara Baase,San Diego,California http://www-rohan.sdsu.edu/faculty/baase Allen Van Gelder,Santa Cruz,Califoria http://www.cse.ucsc.edu/personnel/faculty/avg.html June,1999
Contents Preface vii 1 Analyzing Algorithms and Problems: Principles and Examples 1 1.1 Introduction 2 1.2 Java as an Algorithm Language 3 1.3 Mathematical Background 11 1.4 Analyzing Algorithms and Problems 30 1.5 Classifying Functions by Their Asymptotic Growth Rates 43 1.6 Searching an Ordered Array 53 Exercises 61 Notes and References 67 2 Data Abstraction and Basic Data Structures 69 2.1 Introduction 70 2.2 ADT Specification and Design Techniques 71 2.3 Elementary ADTs-Lists and Trees 73 2.4 Stacks and Queues 86 2.5 ADTs for Dynamic Sets 89 Exercises 95 Notes and References 100 3 Recursion and Induction 101 3.1 Introduction 102 3.2 Recursive Procedures 102 3.3 What Is a Proof？108 3.4 Induction Proofs 111 3.5 Proving Correctness of Procedures 118