Copyright ©2002, by John Wiley & Sons, Inc.. All rights reserved.
This book is designed to provide a comprehensive introduction to the design and analysis of computer algorithms and data structures. In terms of the computer science and computer engineering curricula, we have written this book to be primarily focused on the Junior-Senior level Algorithms (CS7) course, which is taught as a first-year graduate course in some schools.
Professors Goodrich and Tamassia are well-recognized researchers in data structures and algorithms, having published many papers in this field, with applications to Internet computing, information visualization, geographic information systems, and computer security. They have an extensive record of research collaboration and have served as principal investigators in 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 technology research, with special emphasis on algorithm visualization systems and infrastructure support for distance learning.
Michael Goodrich received his Ph.D. in Computer Science from Purdue University in 1987. He is currently a professor in the Department of Information and Computer Science at University of California, Irvine. Prior to this service we was Professor of Computer Science at Johns Hopkins University, and director of the Hopkins Center for Algorithm Engineering. He is an editor for the International Journal of Computational Geometry & Applications, Journal of Computational and System Sciences, and Journal of Graph Algorithms and Applications.
Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1988. He is currently a professor in the Department of Computer Science and the director of the Center for Geometric Computing at Brown University. He is an editor for Computational Geometry: Theory and Applications and the Journal of Graph Algorithms and Applications, and he has previously served on the editorial board of IEEE Transactions on Computers.
In addition to their research accomplishments, the authors also have extensive experience in the classroom. For example, Dr. Goodrich has taught data structures and algorithms courses since 1987, including Data Structures as a freshman-sophomore level course and Introduction to Algorithms as a upper level course. He has earned several teaching awards in this capacity. His teaching style is to involve the students in lively interactive classroom sessions that bring out the intuition and insights behind data structuring and algorithmic techniques, as well as in formulating solutions whose analysis is mathematically rigorous. Dr. Tamassia has taught Data Structures and Algorithms as an introductory freshman-level course since 1988. He has also attracted many students (including several undergraduates) to his advanced course on Computational Geometry, which is a popular graduate-level CS course at Brown. One thing that has set his teaching style apart is his effective use of interactive hypermedia presentations, continuing the tradition of Brown's ``electronic classroom.'' The carefully designed Web pages of the courses taught by Dr. Tamassia have been used as reference material by students and professionals worldwide.
This book is intended primarily as a textbook for a Junior-Senior Algorithms (CS7) course, which is also taught as a first-year graduate course in some schools. This book contains many exercises, which are divided between reinforcement exercises, creativity exercises, and implementation projects. Certain aspects of this book were specifically designed with the instructor in mind, including:
This book is also structured to allow the instructor a great deal of freedom in 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 topics that he or she feels are most important. We have extensively discussed Internet Algorithmics topics, which should prove quite interesting to students. In addition, we have included examples of Internet application of traditional algorithms topics in several places as well.
We show in the table below how this book could be used for a traditional Introduction 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 new Internet-motivated light, while also covering new algorithmic topics that are derived 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 is a mixture of a traditional Introduction to Algorithms (CS7) course and an Internet 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 aids that augment the topics of this book. Specifically for students we include:For instructors using this book, there is a dedicated portion of the Web site just for them, which includes the following additional teaching aids:
Readers interested in the implementation of algorithms and data structures can download JDSL the Data Structures Library in Java, from
We have written this book assuming that the reader comes to it with certain knowledge. In particular, we assume that the reader has a basic understanding of elementary data structures, such as arrays and linked lists, and is at least vaguely familiar with a high-level programming language, such as C, C++, or Java. Even so, all algorithms are described in a high-level ``pseudo-code,'' and specific programming language constructs are only used in the optional Java implementation example sections.
In terms of mathematical background, we assume the reader is familiar with topics from first-year college mathematics, including exponents, logarithms, summations, limits, and elementary probability. Even so, we review most of these facts in Chapter 1, including exponents, logarithms, and summations, and we give a summary of other useful mathematical facts, including elementary probability, in Appendix A.
There are a number of individuals who have helped us with the contents of this book. Specifically, we thank Jeff 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 in developing exercises, programming assignments, and algorithm animation systems. There have been a number of friends and colleagues whose comments have lead to improvements in the text. We are particularly thankful to Karen Goodrich, Art Moorshead, and Scott Smith for their insightful comments. We are also truly indebted to the anonymous outside reviewers for their detailed comments and constructive criticism, which were extremely useful.
We are grateful to our editors, Paul Crockett and Bill Zobrist, for their enthusiastic support of this project. The production team at Wiley has been great. Many thanks go to people who helped us with the book development, including Susannah Barr, Katherine Hepburn, Bonnie Kubat, Sharon Prendergast, Marc Ranger, Jeri Warner, and Jennifer Welter.
This manuscript was prepared primarily with LATEX for the text and Adobe FrameMaker and Visio for the figures. The LGrind system was used to format Java code fragments into LATEX. The CVS version control system enabled smooth coordination of our (sometimes concurrent) file editing.
Trademark Acknowledgments: Java is a trademark of Sun Microsystems, Inc. UNIX is a registered trademark in the United States and other countries, licensed through X/Open Company, Ltd. All other product names mentioned herein are the trademarks of their respective owners.
Finally, we would like to warmly thank Isabel Cruz, Karen Goodrich, Giuseppe Di Battista, Franco Preparata, Ioannis Tollis, and our parents for providing advice, encouragement, and support at various stages of the preparation of this book. We also thank them for reminding us that there are things in life beyond writing books.
