This book is designed to provide a comprehensive introduction to the design and analysis of computeralgorithms and data structures.In terms of the computer science and computer engineeringcurricula, we have written this book to be primarily focused on theJunior-Senior level Algorithms (CS7) course, which is taughtas a first-year graduate course in some schools.
Professors Goodrich and Tamassia are well-recognized researchers indata structures and algorithms, having published many papers in thisfield, with applications to Internet computing, informationvisualization, geographic information systems, and computer security.They have an extensive record of researchcollaboration and have served as principal investigatorsin several joint projects sponsored by the National Science Foundation,the Army Research Office, and the Defense Advanced Research Projects Agency. They are also active in educational technologyresearch, with special emphasis on algorithm visualization systemsand infrastructure support for distance learning.
Michael Goodrich received his Ph.D. in Computer Science from PurdueUniversity in 1987. He is currently a professor in the Department ofInformation and Computer Science at University of California, Irvine.Prior to this service we was Professor ofComputer Science at Johns Hopkins University, and director of theHopkins Center for Algorithm Engineering. He is an editor fortheInternational Journal of Computational Geometry & Applications,Journal of Computational and System Sciences, andJournal of Graph Algorithms and Applications.
Roberto Tamassia received his Ph.D. in Electrical and ComputerEngineering from the University of Illinois at Urbana-Champaignin 1988. He is currently a professor in the Department of ComputerScience and the director of the Center for Geometric Computing atBrown University. He is an editor forComputational Geometry: Theory and Applications and theJournal of Graph Algorithms and Applications, and he has previously served on the editorialboard of IEEETransactions on Computers.
In addition to their research accomplishments, the authors also haveextensive experience in the classroom. For example, Dr. Goodrich hastaught data structures and algorithms courses since 1987, including Data Structures asa freshman-sophomore level course and Introduction to Algorithms as aupper level course. He has earned several teaching awards inthis capacity. His teaching style is to involve the students inlively interactive classroom sessions that bring out the intuitionand insights behind data structuring and algorithmic techniques, aswell as in formulating solutions whose analysis is mathematicallyrigorous.Dr. Tamassia has taught Data Structures and Algorithms as anintroductory freshman-level course since 1988.He has also attracted many students (including severalundergraduates) to his advanced course on Computational Geometry,which is a popular graduate-level CS course at Brown. One thing thathas set his teaching style apart is his effective use of interactivehypermedia presentations, continuing the tradition of Brown's``electronic classroom.'' The carefully designed Web pages of thecourses taught by Dr. Tamassia have been used as reference materialby students and professionals worldwide.
This book is intended primarily as a textbook for aJunior-Senior Algorithms (CS7) course, which is also taught as afirst-year graduate course in some schools.This book contains many exercises, which are divided betweenreinforcement exercises, creativity exercises, and implementation projects.Certain aspects ofthis book were specifically designed with the instructor in mind, including:
This book is also structured to allow the instructor a great deal of freedomin how to organize and present the material. Likewise, the dependence between chapters is rather flexible, allowing the instructor to customize an algorithms course to highlight the topicsthat he or she feels are most important.We have extensively discussedInternet Algorithmics topics, which should prove quite interesting to students.In addition, we have included examples of Internet applicationof traditional algorithms topics in several places as well.
We show in the table below how this book could be used for a traditionalIntroduction to Algorithms (CS7) course, albeit with some new topics motivated from the Internet.
|
This book can also be used for a specialized Internet Algorithmics course,which reviews some traditional algorithms topics, but in a newInternet-motivated light, while also covering new algorithmic topics that arederived from Internet applications.We show in the table below how this book could be used for a such a course.
|
Of course, other options are also possible, including a course that isa mixture of a traditional Introduction to Algorithms (CS7) course and anInternet Algorithmics course. We do not belabor this point, however,leaving such creative arrangements to the interested instructor.
This book comes accompanied by an extensive Web site:
This Web site includes an extensive collection of educational aidsthat augment the topics of this book. Specifically for students weinclude:For instructors using this book, there is a dedicated portion of theWeb site just for them, which includes the following additionalteaching aids:
Readers interested in the implementation of algorithms and datastructures can downloadJDSL theData Structures Library in Java, from
We have written this book assuming that the reader comes to it withcertain knowledge. In particular, we assume that the reader has abasic understanding of elementary data structures, such as arrays andlinked lists, and is at least vaguely familiar witha high-level programming language, such as C, C++, or Java.Even so, all algorithms are described in a high-level ``pseudo-code,'' andspecific programming language constructs are only used in the optional Javaimplementation examplesections.
In terms of mathematical background, we assume the reader is familiar withtopics from first-year college mathematics, includingexponents, logarithms, summations, limits, and elementary probability. Even so, we reviewmost of these facts in Chapter 1,including exponents, logarithms, and summations, and we give a summaryof other useful mathematical facts, including elementary probability,in Appendix A.
There are a number of individuals who have helped us with the contentsof this book. Specifically, we thankJeff Achter, Ryan Baker,Devin Borland,Ulrik Brandes,Stina Bridgeman,Robert Cohen,David Emory,David Ginat,Natasha Gelfand,Mark Handy,Benoît Hudson,Jeremy Mullendore,Daniel Polivy,John Schultz,Andrew Schwerin,Michael Shin,Galina Shubina,and Luca Vismara.
We are grateful to all our former teaching assistants who helped us indeveloping exercises, programming assignments, and algorithm animationsystems. There have been a number of friends and colleagues whosecomments have lead to improvements in the text. We are particularlythankful to Karen Goodrich, Art Moorshead, and Scott Smith for theirinsightful comments. We are also truly indebted to the anonymousoutside reviewers for their detailed comments and constructivecriticism, which were extremely useful.
We are grateful to our editors, Paul Crockett and Bill Zobrist, fortheir enthusiastic support of this project. The production team atWiley has been great. Many thanks go to people who helped us with thebook development, includingSusannah Barr, Katherine Hepburn, Bonnie Kubat,Sharon Prendergast, Marc Ranger,Jeri Warner, and Jennifer Welter.
This manuscript was prepared primarily with LATEX for the text andAdobe FrameMaker and Visio for the figures. The LGrindsystem was used to format Java code fragments into LATEX. The CVSversion control system enabled smooth coordination of our (sometimesconcurrent) file editing.
Trademark Acknowledgments: Java is a trademark of Sun Microsystems, Inc. UNIX is a registered trademark in the United States and othercountries, licensed through X/Open Company, Ltd.All other product names mentioned herein are the trademarks of theirrespective owners.
Finally, we would like to warmly thank Isabel Cruz,Karen Goodrich, Giuseppe Di Battista,Franco Preparata,Ioannis Tollis,and our parents forproviding advice, encouragement, and support at various stages of thepreparation of this book. We also thank them for reminding us that thereare things in life beyond writing books.
