Data Structures and Algorithms in Java (6th ed.) [Goodrich, Tamassia Goldwasser 2014].pdf

www.it-ebooks.info www.it-ebooks.info  Data Structures and Algorithms in Java™ Sixth Edition Michael T. Goodrich Department of Computer Science University of California, Irvine Roberto Tamassia Department of Computer Science...

www.it-ebooks.info www.it-ebooks.info  Data Structures and Algorithms in Java™ Sixth Edition Michael T. Goodrich Department of Computer Science University of California, Irvine Roberto Tamassia Department of Computer Science Brown University Michael H. Goldwasser Department of Mathematics and Computer Science Saint Louis University www.it-ebooks.info  Vice President and Executive Publisher Don Fowley Executive Editor Beth Lang Golub Assistant Marketing Manager Debbie Martin Sponsoring Editor Mary O’Sullivan Project Editor Ellen Keohane Associate Production Manager Joyce Poh Cover Designer Kenji Ngieng This book was set in LATEX by the authors, and printed and bound by RR Donnelley. The cover was printed by RR Donnelley. Trademark Acknowledgments: Java is a trademark of Oracle Corporation. Unix ® is a registered trademark in the United States and other countries, licensed through X/Open Company, Ltd. PowerPoint ® is a trademark of Microsoft Corporation. All other product names mentioned herein are the trademarks of their respective owners. This book is printed on acid free paper. Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/citizenship. Copyright © 2014, 2010 John Wiley & Sons, Inc. All rights reserved. No part of this publi- cation may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, with- out either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201) 748-6011, fax (201) 748-6008, website http://www.wiley.com/go/ permissions. Evaluation copies are provided to qualified academics and professionals for review pur- poses only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative. ISBN: 978-1-118-77133-4 (paperback) Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 www.it-ebooks.info To Karen, Paul, Anna, and Jack – Michael T. Goodrich To Isabel – Roberto Tamassia To Susan, Calista, and Maya – Michael H. Goldwasser www.it-ebooks.info www.it-ebooks.info Preface to the Sixth Edition Data Structures and Algorithms in Java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. The major changes in this sixth edition include the following: We redesigned the entire code base to increase clarity of presentation and consistency in style and convention, including reliance on type inference, as introduced in Java 7, to reduce clutter when instantiating generic types. We added 38 new figures, and redesigned 144 existing figures. We revised and expanded exercises, bringing the grand total to 794 exercises! We continue our approach of dividing them into reinforcement, creativity, and project exercises. However, we have chosen not to reset the number- ing scheme with each new category, thereby avoiding possible ambiguity between exercises such as R-7.5, C-7.5, P-7.5. The introductory chapters contain additional examples of classes and inheri- tance, increased discussion of Java’s generics framework, and expanded cov- erage of cloning and equivalence testing in the context of data structures. A new chapter, dedicated to the topic of recursion, provides comprehensive coverage of material that was previously divided within Chapters 3, 4, and 9 of the fifth edition, while newly introducing the use of recursion when processing file systems. We provide a new empirical study of the efficiency of Java’s StringBuilder class relative to the repeated concatenation of strings, and then discuss the theoretical underpinnings of its amortized performance. We provide increased discussion of iterators, contrasting between so-called lazy iterators and snapshot iterators, with examples of both styles of imple- mentation for several data structures. We have increased the use of abstract base classes to reduce redundancy when providing multiple implementations of a common interface, and the use of nested classes to provide greater encapsulation for our data structures. We have included complete Java implementations for many data structures and algorithms that were only described with pseudocode in earlier editions. These new implementations include both array-based and linked-list-based queue implementations, a heap-based adaptable priority queue, a bottom-up heap construction, hash tables with either separate chaining or linear probing, splay trees, dynamic programming for the least-common subsequence prob- lem, a union-find data structure with path compression, breadth-first search of a graph, the Floyd-Warshall algorithm for computing a graph’s transitive closure, topological sorting of a DAG, and both the Prim-Jarnı́k and Kruskal algorithms for computing a minimum spanning tree. v www.it-ebooks.info vi Preface Prerequisites We assume that the reader is at least vaguely familiar with a high-level program- ming language, such as C, C++, Python, or Java, and that he or she understands the main constructs from such a high-level language, including: Variables and expressions Methods (also known as functions or procedures) Decision structures (such as if-statements and switch-statements) Iteration structures (for-loops and while-loops) For readers who are familiar with these concepts, but not with how they are ex- pressed in Java, we provide a primer on the Java language in Chapter 1. Still, this book is primarily a data structures book, not a Java book; hence, it does not provide a comprehensive treatment of Java. Nevertheless, we do not assume that the reader is necessarily familiar with object-oriented design or with linked structures, such as linked lists, for these topics are covered in the core chapters of this book. In terms of mathematical background, we assume the reader is somewhat famil- iar with topics from high-school mathematics. Even so, in Chapter 4, we discuss the seven most-important functions for algorithm analysis. In fact, sections that use something other than one of these seven functions are considered optional, and are indicated with a star (⋆). Online Resources This book is accompanied by an extensive set of online resources, which can be found at the following website: www.wiley.com/college/goodrich Included on this website is a collection of educational aids that augment the topics of this book, for both students and instructors. For all readers, and especially for students, we include the following resources: All Java source code presented in this book An appendix of useful mathematical facts PDF handouts of PowerPoint slides (four-per-page) A study guide with hints to exercises, indexed by problem number For instructors using this book, we include the following additional teaching aids: Solutions to hundreds of the book’s exercises Color versions of all figures and illustrations from the book Slides in PowerPoint and PDF (one-per-page) format The slides are fully editable, so as to allow an instructor using this book full free- dom in customizing his or her presentations. www.it-ebooks.info Preface vii Use as a Textbook The design and analysis of efficient data structures has long been recognized as a core subject in computing. We feel that the central role of data structure design and analysis in the curriculum is fully justified, given the importance of efficient data structures and algorithms in most software systems, including the Web, operating systems, databases, compilers, and scientific simulation systems. This book is designed for use in a beginning-level data structures course, or in an intermediate-level introduction to algorithms course. The chapters for this book are organized to provide a pedagogical path that starts with the basics of Java programming and object-oriented design. We then discuss concrete structures in- cluding arrays and linked lists, and foundational techniques like algorithm analysis and recursion. In the main portion of the book we present fundamental data struc- tures and algorithms, concluding with a discussion of memory management. A detailed table of contents follows this preface, beginning on page x. To assist instructors in designing a course in the context of the IEEE/ACM 2013 Computing Curriculum, the following table describes curricular knowledge units that are covered within this book. Knowledge Unit Relevant Material AL/Basic Analysis Chapter 4 and Sections 5.2 & 12.1.4 Sections 5.3.3, 12.1.1, 13.2.1, 13.4.2, 13.5, AL/Algorithmic Strategies 14.6.2 & 14.7 AL/Fundamental Data Structures Sections 3.1.2, 5.1.3, 9.3, 9.4.1, 10.2, 11.1, and Algorithms 13.2, and Chapters 12 & 14 Sections 7.2.1, 10.4, 11.2–11.6, 12.2.1, 13.3, AL/Advanced Data Structures 14.5.1 & 15.3 AR/Memory System Organization Chapter 15 and Architecture DS/Sets, Relations, and Functions Sections 9.2.2 & 10.5 DS/Proof Techniques Sections 4.4, 5.2, 7.2.3, 9.3.4 & 12.3.1 DS/Basics of Counting Sections 2.2.3, 6.2.2, 8.2.2 & 12.1.4. DS/Graphs and Trees Chapters 8 and 14 DS/Discrete Probability Sections 3.1.3, 10.2, 10.4.2 & 12.2.1 PL/Object-Oriented Programming Chapter 2 and Sections 7.3, 9.5.1 & 11.2.1 SDF/Algorithms and Design Sections 2.1, 4.3 & 12.1.1 SDF/Fundamental Programming Chapters 1 & 5 Concepts SDF/Fundamental Data Structures Chapters 3 & 6, and Sections 1.3, 9.1 & 10.1 SDF/Developmental Methods Sections 1.9 & 2.4 SE/Software Design Section 2.1 Mapping the IEEE/ACM 2013 Computing Curriculum knowledge units to coverage within this book. www.it-ebooks.info viii Preface About the Authors Michael Goodrich received his Ph.D. in Computer Science from Purdue University in 1987. He is currently a Chancellor’s Professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. He is a Fulbright Scholar and a Fellow of the American As- sociation for the Advancement of Science (AAAS), Association for Computing Machinery (ACM), and Institute of Electrical and Electronics Engineers (IEEE). He is a recipient of the IEEE Computer Society Technical Achievement Award, the ACM Recognition of Service Award, and the Pond Award for Excellence in Undergraduate Teaching. Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana–Champaign in 1988. He is the Plastech Professor of Computer Science and the Chair of the Department of Computer Sci- ence at Brown University. He is also the Director of Brown’s Center for Geometric Computing. His research interests include information security, cryptography, anal- ysis, design, and implementation of algorithms, graph drawing, and computational geometry. He is a Fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM) and Institute for Electrical and Electronic Engineers (IEEE). He is a recipient of the IEEE Computer Society Technical Achievement Award. Michael Goldwasser received his Ph.D. in Computer Science from Stanford University in 1997. He is currently Professor and Director of the Computer Science program in the Department of Mathematics and Computer Science at Saint Louis University. He was previously a faculty member in the Department of Computer Science at Loyola University Chicago. His research interests focus on the design and implementation of algorithms, having published work involving approximation algorithms, online computation, computational biology, and computational geom- etry. He is also active in the computer science education community. Additional Books by These Authors Di Battista, Eades, Tamassia, and Tollis, Graph Drawing, Prentice Hall Goodrich, Tamassia, and Goldwasser, Data Structures and Algorithms in Python, Wiley Goodrich, Tamassia, and Mount, Data Structures and Algorithms in C++, Wiley Goodrich and Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley Goodrich and Tamassia, Introduction to Computer Security, Addison-Wesley Goldwasser and Letscher, Object-Oriented Programming in Python, Prentice Hall www.it-ebooks.info Preface ix Acknowledgments There are so many individuals who have made contributions to the development of this book over the past decade, it is difficult to name them all. We wish to reit- erate our thanks to the many research collaborators and teaching assistants whose feedback shaped the previous versions of this material. The benefits of those con- tributions carry forward to this book. For the sixth edition, we are indebted to the outside reviewers and readers for their copious comments, emails, and constructive criticisms. We therefore thank the following people for their comments and suggestions: Sameer O. Abufardeh (North Dakota State University), Mary Boelk (Marquette University), Frederick Crabbe (United States Naval Academy), Scot Drysdale (Dartmouth College), David Eisner, Henry A. Etlinger (Rochester Institute of Technology), Chun-Hsi Huang (Univer- sity of Connecticut), John Lasseter (Hobart and William Smith Colleges), Yupeng Lin, Suely Oliveira (University of Iowa), Vincent van Oostrom (Utrecht Univer- sity), Justus Piater (University of Innsbruck), Victor I. Shtern (Boston University), Tim Soethout, and a number of additional anonymous reviewers. There have been a number of friends and colleagues whose comments have led to improvements in the text. We are particularly thankful to Erin Chambers, Karen Goodrich, David Letscher, David Mount, and Ioannis Tollis for their insightful comments. In addition, contributions by David Mount to the coverage of recursion and to several figures are gratefully acknowledged. We appreciate the wonderful team at Wiley, including our editor, Beth Lang Golub, for her enthusiastic support of this project from beginning to end, and the Product Solutions Group editors, Mary O’Sullivan and Ellen Keohane, for carrying the project to its completion. The quality of this book is greatly enhanced as a result of the attention to detail demonstrated by our copyeditor, Julie Kennedy. The final months of the production process were gracefully managed by Joyce Poh. Finally, we would like to warmly thank Karen Goodrich, Isabel Cruz, Susan Goldwasser, Giuseppe Di Battista, Franco Preparata, Ioannis Tollis, and our parents for providing advice, encouragement, and support at various stages of the prepa- ration of this book, and Calista and Maya Goldwasser for offering their advice regarding the artistic merits of many illustrations. More importantly, we thank all of these people for reminding us that there are things in life beyond writing books. Michael T. Goodrich Roberto Tamassia Michael H. Goldwasser www.it-ebooks.info  Contents 1 Java Primer 1 1.1 Getting Started............................. 2 1.1.1 Base Types............................ 4 1.2 Classes and Objects........................... 5 1.2.1 Creating and Using Objects.................... 6 1.2.2 Defining a Class.......................... 9 1.3 Strings, Wrappers, Arrays, and Enum Types............. 17 1.4 Expressions................................ 23 1.4.1 Literals............................... 23 1.4.2 Operators............................. 24 1.4.3 Type Conversions......................... 28 1.5 Control Flow............................... 30 1.5.1 The If and Switch Statements.................. 30 1.5.2 Loops............................... 33 1.5.3 Explicit Control-Flow Statements................. 37 1.6 Simple Input and Output........................ 38 1.7 An Example Program.......................... 41 1.8 Packages and Imports.......................... 44 1.9 Software Development......................... 46 1.9.1 Design............................... 46 1.9.2 Pseudocode............................ 48 1.9.3 Coding............................... 49 1.9.4 Documentation and Style..................... 50 1.9.5 Testing and Debugging...................... 53 1.10 Exercises................................. 55 2 Object-Oriented Design 59 2.1 Goals, Principles, and Patterns.................... 60 2.1.1 Object-Oriented Design Goals.................. 60 2.1.2 Object-Oriented Design Principles................ 61 2.1.3 Design Patterns.......................... 63 2.2 Inheritance................................ 64 2.2.1 Extending the CreditCard Class.................. 65 2.2.2 Polymorphism and Dynamic Dispatch.............. 68 2.2.3 Inheritance Hierarchies...................... 69 2.3 Interfaces and Abstract Classes.................... 76 2.3.1 Interfaces in Java......................... 76 2.3.2 Multiple Inheritance for Interfaces................ 79 2.3.3 Abstract Classes.......................... 80 2.4 Exceptions................................ 82 2.4.1 Catching Exceptions........................ 82 2.4.2 Throwing Exceptions....................... 85 2.4.3 Java’s Exception Hierarchy.................... 86 2.5 Casting and Generics.......................... 88 x www.it-ebooks.info Contents xi 2.5.1 Casting.............................. 88 2.5.2 Generics.............................. 91 2.6 Nested Classes.............................. 96 2.7 Exercises................................. 97 3 Fundamental Data Structures 103 3.1 Using Arrays............................... 104 3.1.1 Storing Game Entries in an Array................. 104 3.1.2 Sorting an Array.......................... 110 3.1.3 java.util Methods for Arrays and Random Numbers....... 112 3.1.4 Simple Cryptography with Character Arrays........... 115 3.1.5 Two-Dimensional Arrays and Positional Games......... 118 3.2 Singly Linked Lists............................ 122 3.2.1 Implementing a Singly Linked List Class............. 126 3.3 Circularly Linked Lists.......................... 128 3.3.1 Round-Robin Scheduling..................... 128 3.3.2 Designing and Implementing a Circularly Linked List...... 129 3.4 Doubly Linked Lists........................... 132 3.4.1 Implementing a Doubly Linked List Class............ 135 3.5 Equivalence Testing........................... 138 3.5.1 Equivalence Testing with Arrays................. 139 3.5.2 Equivalence Testing with Linked Lists.............. 140 3.6 Cloning Data Structures........................ 141 3.6.1 Cloning Arrays........................... 142 3.6.2 Cloning Linked Lists........................ 144 3.7 Exercises................................. 145 4 Algorithm Analysis 149 4.1 Experimental Studies.......................... 151 4.1.1 Moving Beyond Experimental Analysis.............. 154 4.2 The Seven Functions Used in This Book............... 156 4.2.1 Comparing Growth Rates..................... 163 4.3 Asymptotic Analysis........................... 164 4.3.1 The “Big-Oh” Notation...................... 164 4.3.2 Comparative Analysis....................... 168 4.3.3 Examples of Algorithm Analysis................. 170 4.4 Simple Justification Techniques.................... 178 4.4.1 By Example............................ 178 4.4.2 The “Contra” Attack....................... 178 4.4.3 Induction and Loop Invariants.................. 179 4.5 Exercises................................. 182 5 Recursion 189 5.1 Illustrative Examples.......................... 191 5.1.1 The Factorial Function...................... 191 5.1.2 Drawing an English Ruler..................... 193 5.1.3 Binary Search........................... 196 www.it-ebooks.info xii Contents 5.1.4 File Systems............................ 198 5.2 Analyzing Recursive Algorithms.................... 202 5.3 Further Examples of Recursion..................... 206 5.3.1 Linear Recursion.......................... 206 5.3.2 Binary Recursion......................... 211 5.3.3 Multiple Recursion........................ 212 5.4 Designing Recursive Algorithms.................... 214 5.5 Recursion Run Amok.......................... 215 5.5.1 Maximum Recursive Depth in Java................ 218 5.6 Eliminating Tail Recursion....................... 219 5.7 Exercises................................. 221 6 Stacks, Queues, and Deques 225 6.1 Stacks................................... 226 6.1.1 The Stack Abstract Data Type.................. 227 6.1.2 A Simple Array-Based Stack Implementation.......... 230 6.1.3 Implementing a Stack with a Singly Linked List......... 233 6.1.4 Reversing an Array Using a Stack................ 234 6.1.5 Matching Parentheses and HTML Tags............. 235 6.2 Queues.................................. 238 6.2.1 The Queue Abstract Data Type................. 239 6.2.2 Array-Based Queue Implementation............... 241 6.2.3 Implementing a Queue with a Singly Linked List......... 245 6.2.4 A Circular Queue......................... 246 6.3 Double-Ended Queues.......................... 248 6.3.1 The Deque Abstract Data Type................. 248 6.3.2 Implementing a Deque...................... 250 6.3.3 Deques in the Java Collections Framework............ 251 6.4 Exercises................................. 252 7 List and Iterator ADTs 257 7.1 The List ADT.............................. 258 7.2 Array Lists................................ 260 7.2.1 Dynamic Arrays.......................... 263 7.2.2 Implementing a Dynamic Array.................. 264 7.2.3 Amortized Analysis of Dynamic Arrays.............. 265 7.2.4 Java’s StringBuilder class..................... 269 7.3 Positional Lists.............................. 270 7.3.1 Positions.............................. 272 7.3.2 The Positional List Abstract Data Type............. 272 7.3.3 Doubly Linked List Implementation................ 276 7.4 Iterators.................................. 282 7.4.1 The Iterable Interface and Java’s For-Each Loop........ 283 7.4.2 Implementing Iterators...................... 284 7.5 The Java Collections Framework................... 288 7.5.1 List Iterators in Java....................... 289 7.5.2 Comparison to Our Positional List ADT............. 290 www.it-ebooks.info Contents xiii 7.5.3 List-Based Algorithms in the Java Collections Framework.... 291 7.6 Sorting a Positional List........................ 293 7.7 Case Study: Maintaining Access Frequencies............ 294 7.7.1 Using a Sorted List........................ 294 7.7.2 Using a List with the Move-to-Front Heuristic.......... 297 7.8 Exercises................................. 300 8 Trees 307 8.1 General Trees............................... 308 8.1.1 Tree Definitions and Properties.................. 309 8.1.2 The Tree Abstract Data Type.................. 312 8.1.3 Computing Depth and Height................... 314 8.2 Binary Trees............................... 317 8.2.1 The Binary Tree Abstract Data Type............... 319 8.2.2 Properties of Binary Trees.................... 321 8.3 Implementing Trees........................... 323 8.3.1 Linked Structure for Binary Trees................. 323 8.3.2 Array-Based Representation of a Binary Tree.......... 331 8.3.3 Linked Structure for General Trees................ 333 8.4 Tree Traversal Algorithms....................... 334 8.4.1 Preorder and Postorder Traversals of General Trees....... 334 8.4.2 Breadth-First Tree Traversal................... 336 8.4.3 Inorder Traversal of a Binary Tree................ 337 8.4.4 Implementing Tree Traversals in Java.............. 339 8.4.5 Applications of Tree Traversals.................. 343 8.4.6 Euler Tours............................ 348 8.5 Exercises................................. 350 9 Priority Queues 359 9.1 The Priority Queue Abstract Data Type............... 360 9.1.1 Priorities.............................. 360 9.1.2 The Priority Queue ADT..................... 361 9.2 Implementing a Priority Queue.................... 362 9.2.1 The Entry Composite....................... 362 9.2.2 Comparing Keys with Total Orders................ 363 9.2.3 The AbstractPriorityQueue Base Class.............. 364 9.2.4 Implementing a Priority Queue with an Unsorted List...... 366 9.2.5 Implementing a Priority Queue with a Sorted List........ 368 9.3 Heaps................................... 370 9.3.1 The Heap Data Structure..................... 370 9.3.2 Implementing a Priority Queue with a Heap........... 372 9.3.3 Analysis of a Heap-Based Priority Queue............. 379 9.3.4 Bottom-Up Heap Construction ⋆................ 380 9.3.5 Using the java.util.PriorityQueue Class.............. 384 9.4 Sorting with a Priority Queue..................... 385 9.4.1 Selection-Sort and Insertion-Sort................. 386 9.4.2 Heap-Sort............................. 388 www.it-ebooks.info xiv Contents 9.5 Adaptable Priority Queues....................... 390 9.5.1 Location-Aware Entries...................... 391 9.5.2 Implementing an Adaptable Priority Queue........... 392 9.6 Exercises................................. 395 10 Maps, Hash Tables, and Skip Lists 401 10.1 Maps................................... 402 10.1.1 The Map ADT.......................... 403 10.1.2 Application: Counting Word Frequencies............. 405 10.1.3 An AbstractMap Base Class................... 406 10.1.4 A Simple Unsorted Map Implementation............. 408 10.2 Hash Tables............................... 410 10.2.1 Hash Functions.......................... 411 10.2.2 Collision-Handling Schemes.................... 417 10.2.3 Load Factors, Rehashing, and Efficiency............. 420 10.2.4 Java Hash Table Implementation................. 422 10.3 Sorted Maps............................... 428 10.3.1 Sorted Search Tables....................... 429 10.3.2 Two Applications of Sorted Maps................ 433 10.4 Skip Lists................................. 436 10.4.1 Search and Update Operations in a Skip List.......... 438 ⋆ 10.4.2 Probabilistic Analysis of Skip Lists............... 442 10.5 Sets, Multisets, and Multimaps.................... 445 10.5.1 The Set ADT........................... 445 10.5.2 The Multiset ADT........................ 447 10.5.3 The Multimap ADT........................ 448 10.6 Exercises................................. 451 11 Search Trees 459 11.1 Binary Search Trees........................... 460 11.1.1 Searching Within a Binary Search Tree.............. 461 11.1.2 Insertions and Deletions...................... 463 11.1.3 Java Implementation....................... 466 11.1.4 Performance of a Binary Search Tree............... 470 11.2 Balanced Search Trees......................... 472 11.2.1 Java Framework for Balancing Search Trees........... 475 11.3 AVL Trees................................. 479 11.3.1 Update Operations........................ 481 11.3.2 Java Implementation....................... 486 11.4 Splay Trees................................ 488 11.4.1 Splaying.............................. 488 11.4.2 When to Splay........................... 492 11.4.3 Java Implementation....................... 494 11.4.4 Amortized Analysis of Splaying ⋆................ 495 11.5 (2,4) Trees................................ 500 11.5.1 Multiway Search Trees...................... 500 11.5.2 (2,4)-Tree Operations....................... 503 www.it-ebooks.info Contents xv 11.6 Red-Black Trees............................. 510 11.6.1 Red-Black Tree Operations.................... 512 11.6.2 Java Implementation....................... 522 11.7 Exercises................................. 525 12 Sorting and Selection 531 12.1 Merge-Sort................................ 532 12.1.1 Divide-and-Conquer........................ 532 12.1.2 Array-Based Implementation of Merge-Sort........... 537 12.1.3 The Running Time of Merge-Sort................ 538 12.1.4 Merge-Sort and Recurrence Equations..... ⋆........ 540 12.1.5 Alternative Implementations of Merge-Sort........... 541 12.2 Quick-Sort................................ 544 12.2.1 Randomized Quick-Sort...................... 551 12.2.2 Additional Optimizations for Quick-Sort............. 553 12.3 Studying Sorting through an Algorithmic Lens........... 556 12.3.1 Lower Bound for Sorting..................... 556 12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort........ 558 12.4 Comparing Sorting Algorithms..................... 561 12.5 Selection................................. 563 12.5.1 Prune-and-Search......................... 563 12.5.2 Randomized Quick-Select..................... 564 12.5.3 Analyzing Randomized Quick-Select............... 565 12.6 Exercises................................. 566 13 Text Processing 573 13.1 Abundance of Digitized Text...................... 574 13.1.1 Notations for Character Strings.................. 575 13.2 Pattern-Matching Algorithms..................... 576 13.2.1 Brute Force............................ 576 13.2.2 The Boyer-Moore Algorithm................... 578 13.2.3 The Knuth-Morris-Pratt Algorithm................ 582 13.3 Tries.................................... 586 13.3.1 Standard Tries........................... 586 13.3.2 Compressed Tries......................... 590 13.3.3 Suffix Tries............................ 592 13.3.4 Search Engine Indexing...................... 594 13.4 Text Compression and the Greedy Method............. 595 13.4.1 The Huffman Coding Algorithm................. 596 13.4.2 The Greedy Method........................ 597 13.5 Dynamic Programming......................... 598 13.5.1 Matrix Chain-Product....................... 598 13.5.2 DNA and Text Sequence Alignment............... 601 13.6 Exercises................................. 605 www.it-ebooks.info xvi Contents 14 Graph Algorithms 611 14.1 Graphs................................... 612 14.1.1 The Graph ADT.......................... 618 14.2 Data Structures for Graphs....................... 619 14.2.1 Edge List Structure........................ 620 14.2.2 Adjacency List Structure..................... 622 14.2.3 Adjacency Map Structure..................... 624 14.2.4 Adjacency Matrix Structure.................... 625 14.2.5 Java Implementation....................... 626 14.3 Graph Traversals............................. 630 14.3.1 Depth-First Search........................ 631 14.3.2 DFS Implementation and Extensions............... 636 14.3.3 Breadth-First Search....................... 640 14.4 Transitive Closure............................ 643 14.5 Directed Acyclic Graphs........................ 647 14.5.1 Topological Ordering....................... 647 14.6 Shortest Paths.............................. 651 14.6.1 Weighted Graphs......................... 651 14.6.2 Dijkstra’s Algorithm........................ 653 14.7 Minimum Spanning Trees........................ 662 14.7.1 Prim-Jarnı́k Algorithm...................... 664 14.7.2 Kruskal’s Algorithm........................ 667 14.7.3 Disjoint Partitions and Union-Find Structures.......... 672 14.8 Exercises................................. 677 15 Memory Management and B-Trees 687 15.1 Memory Management.......................... 688 15.1.1 Stacks in the Java Virtual Machine................ 688 15.1.2 Allocating Space in the Memory Heap.............. 691 15.1.3 Garbage Collection........................ 693 15.2 Memory Hierarchies and Caching................... 695 15.2.1 Memory Systems......................... 695 15.2.2 Caching Strategies........................ 696 15.3 External Searching and B-Trees.................... 701 15.3.1 (a, b) Trees............................ 702 15.3.2 B-Trees.............................. 704 15.4 External-Memory Sorting........................ 705 15.4.1 Multiway Merging......................... 706 15.5 Exercises................................. 707 Bibliography 710 Index 714 Useful Mathematical Facts available at www.wiley.com/college/goodrich www.it-ebooks.info Chapter 1 Java Primer Contents 1.1 Getting Started........................ 2 1.1.1 Base Types......................... 4 1.2 Classes and Objects...................... 5 1.2.1 Creating and Using Objects................. 6 1.2.2 Defining a Class....................... 9 1.3 Strings, Wrappers, Arrays, and Enum Types........ 17 1.4 Expressions........................... 23 1.4.1 Literals............................ 23 1.4.2 Operators.......................... 24 1.4.3 Type Conversions...................... 28 1.5 Control Flow.......................... 30 1.5.1 The If and Switch Statements............... 30 1.5.2 Loops............................ 33 1.5.3 Explicit Control-Flow Statements.............. 37 1.6 Simple Input and Output................... 38 1.7 An Example Program..................... 41 1.8 Packages and Imports..................... 44 1.9 Software Development.................... 46 1.9.1 Design............................ 46 1.9.2 Pseudocode......................... 48 1.9.3 Coding............................ 49 1.9.4 Documentation and Style.................. 50 1.9.5 Testing and Debugging................... 53 1.10 Exercises............................ 55 www.it-ebooks.info 2 Chapter 1. Java Primer 1.1 Getting Started Building data structures and algorithms requires that we communicate detailed in- structions to a computer. An excellent way to perform such communication is using a high-level computer language, such as Java. In this chapter, we provide an overview of the Java programming language, and we continue this discussion in the next chapter, focusing on object-oriented design principles. We assume that readers are somewhat familiar with an existing high-level language, although not necessar- ily Java. This book does not provide a complete description of the Java language (there are numerous language references for that purpose), but it does introduce all aspects of the language that are used in code fragments later in this book. We begin our Java primer with a program that prints “Hello Universe!” on the screen, which is shown in a dissected form in Figure 1.1. Figure 1.1: A “Hello Universe!” program. In Java, executable statements are placed in functions, known as methods, that belong to class definitions. The Universe class, in our first example, is extremely simple; its only method is a static one named main, which is the first method to be executed when running a Java program. Any set of statements between the braces “{” and “}” define a program block. Notice that the entire Universe class definition is delimited by such braces, as is the body of the main method. The name of a class, method, or variable in Java is called an identifier, which can be any string of characters as long as it begins with a letter and consists of let- ters, numbers, and underscore characters (where “letter” and “number” can be from any written language defined in the Unicode character set). We list the exceptions to this general rule for Java identifiers in Table 1.1. www.it-ebooks.info 1.1. Getting Started 3 Reserved Words abstract default goto package synchronized assert do if private this boolean double implements protected throw break else import public throws byte enum instanceof return transient case extends int short true catch false interface static try char final long strictfp void class finally native super volatile const float new switch while continue for null Table 1.1: A listing of the reserved words in Java. These names cannot be used as class, method, or variable names. Comments In addition to executable statements and declarations, Java allows a programmer to embed comments, which are annotations provided for human readers that are not processed by the Java compiler. Java allows two kinds of comments: inline comments and block comments. Java uses a “//” to begin an inline comment, ignoring everything subsequently on that line. For example: // This is an inline comment. We will intentionally color all comments in blue in this book, so that they are not confused with executable code. While inline comments are limited to one line, Java allows multiline comments in the form of block comments. Java uses a “” to close it. For example: Block comments that begin with “”, and each line between these two can begin with a single asterisk, “*”, which is ignored. The block comment is assumed to start with a descriptive sentence, which is followed by special lines that begin with javadoc tags. A block comment that comes just before a class definition, instance variable declaration, or method definition is processed by javadoc into a comment about that class, variable, or method. The primary javadoc tags that we use are the following: @author text: Identifies each author (one per line) for a class. @throws exceptionName description: Identifies an error condition that is signaled by this method (see Section 2.4). @param parameterName description: Identifies a parameter accepted by this method. @return description: Describes the return type and its range of values for a method. There are other tags as well; the interested reader is referred to online documen- tation for javadoc for further information. For space reasons, we cannot always include javadoc-style comments in all the example programs included in this book, but we include such a sample in Code Fragment 1.8, and within the online code at the website that accompanies this book. Figure 1.6: Documentation rendered by javadoc for the CreditCard.charge method. www.it-ebooks.info 1.9. Software Development 51 1 /∗∗ 2 ∗ A simple model for a consumer credit card. 3 ∗ 4 ∗ @author Michael T. Goodrich 5 ∗ @author Roberto Tamassia 6 ∗ @author Michael H. Goldwasser 7 ∗/ 8 public class CreditCard { 9 /∗∗ 10 ∗ Constructs a new credit card instance. 11 ∗ @param cust the name of the customer (e.g., ”John Bowman”) 12 ∗ @param bk the name of the bank (e.g., ”California Savings”) 13 ∗ @param acnt the account identifier (e.g., ”5391 0375 9387 5309”) 14 ∗ @param lim the credit limit (measured in dollars) 15 ∗ @param initialBal the initial balance (measured in dollars) 16 ∗/ 17 public CreditCard(String cust, String bk, String acnt, int lim, double initialBal) { 18 customer = cust; 19 bank = bk; 20 account = acnt; 21 limit = lim; 22 balance = initialBal; 23 } 24 25 /∗∗ 26 ∗ Charges the given price to the card, assuming sufficient credit limit. 27 ∗ @param price the amount to be charged 28 ∗ @return true if charge was accepted; false if charge was denied 29 ∗/ 30 public boolean charge(double price) { // make a charge 31 if (price + balance > limit) // if charge would surpass limit 32 return false; // refuse the charge 33 // at this point, the charge is successful 34 balance += price; // update the balance 35 return true; // announce the good news 36 } 37 38 /∗∗ 39 ∗ Processes customer payment that reduces balance. 40 ∗ @param amount the amount of payment made 41 ∗/ 42 public void makePayment(double amount) { // make a payment 43 balance −= amount; 44 } 45 // remainder of class omitted... Code Fragment 1.8: A portion of the CreditCard class definition, originally from Code Fragment 1.5, with javadoc-style comments included. www.it-ebooks.info 52 Chapter 1. Java Primer Readability and Programming Conventions Programs should be made easy to read and understand. Good programmers should therefore be mindful of their coding style, and develop a style that communicates the important aspects of a program’s design for both humans and computers. Much has been written about good coding style, with some of the main principles being the following: Use meaningful names for identifiers. Try to choose names that can be read aloud, and choose names that reflect the action, responsibility, or data each identifier is naming. The tradition in most Java circles is to capitalize the first letter of each word in an identifier, except for the first word for a variable or method name. By this convention, “Date,” “Vector,” “DeviceManager” would identify classes, and “isFull( ),” “insertItem( ),” “studentName,” and “studentHeight” would respectively identify methods and variables. Use named constants or enum types instead of literals. Readability, robust- ness, and modifiability are enhanced if we include a series of definitions of named constant values in a class definition. These can then be used within this class and others to refer to special values for this class. The tradition in Java is to fully capitalize such constants, as shown below: public class Student { public static final int MIN CREDITS = 12; // min credits per term public static final int MAX CREDITS = 24; // max credits per term public enum Year {FRESHMAN, SOPHOMORE, JUNIOR, SENIOR}; // Instance variables, constructors, and method definitions go here... } Indent statement blocks. Typically programmers indent each statement block by 4 spaces; in this book we typically use 2 spaces, however, to avoid having our code overrun the book’s margins. Organize each class in the following order: 1. Constants 2. Instance variables 3. Constructors 4. Methods We note that some Java programmers prefer to put instance variable defini- tions last. We put them earlier so that we can read each class sequentially and understand the data each method is working with. Use comments that add meaning to a program and explain ambiguous or confusing constructs. In-line comments are good for quick explanations and do not need to be sentences. Block comments are good for explaining the purpose of a method and complex code sections. www.it-ebooks.info 1.9. Software Development 53 1.9.5 Testing and Debugging Testing is the process of experimentally checking the correctness of a program, while debugging is the process of tracking the execution of a program and discov- ering the errors in it. Testing and debugging are often the most time-consuming activity in the development of a program. Testing A careful testing plan is an essential part of writing a program. While verifying the correctness of a program over all possible inputs is usually infeasible, we should aim at executing the program on a representative subset of inputs. At the very minimum, we should make sure that every method of a program is tested at least once (method coverage). Even better, each code statement in the program should be executed at least once (statement coverage). Programs often tend to fail on special cases of the input. Such cases need to be carefully identified and tested. For example, when testing a method that sorts (that is, puts in order) an array of integers, we should consider the following inputs: The array has zero length (no elements). The array has one element. All the elements of the array are the same. The array is already sorted. The array is reverse sorted. In addition to special inputs to the program, we should also consider special conditions for the structures used by the program. For example, if we use an array to store data, we should make sure that boundary cases, such as inserting or removing at the beginning or end of the subarray holding data, are properly handled. While it is essential to use handcrafted test suites, it is also advantageous to run the program on a large collection of randomly generated inputs. The Random class in the java.util package provides several means for generating pseudorandom numbers. There is a hierarchy among the classes and methods of a program induced by the caller-callee relationship. Namely, a method A is above a method B in the hierarchy if A calls B. There are two main testing strategies, top-down testing and bottom-up testing, which differ in the order in which methods are tested. Top-down testing proceeds from the top to the bottom of the program hierar- chy. It is typically used in conjunction with stubbing, a boot-strapping technique that replaces a lower-level method with a stub, a replacement for the method that simulates the functionality of the original. For example, if method A calls method B to get the first line of a file, when testing A we can replace B with a stub that returns a fixed string. www.it-ebooks.info 54 Chapter 1. Java Primer Bottom-up testing proceeds from lower-level methods to higher-level methods. For example, bottom-level methods, which do not invoke other methods, are tested first, followed by methods that call only bottom-level methods, and so on. Similarly a class that does not depend upon any other classes can be tested before another class that depends on the former. This form of testing is usually described as unit testing, as the functionality of a specific component is tested in isolation of the larger software project. If used properly, this strategy better isolates the cause of errors to the component being tested, as lower-level components upon which it relies should have already been thoroughly tested. Java provides several forms of support for automated testing. We have already discussed how a class’s static main method can be repurposed to perform tests of the functionality of that class (as was done in Code 1.6 for the CreditCard class). Such a test can be executed by invoking the Java virtual machine directly on this secondary class, rather than on the primary class for the entire application. When Java is started on the primary class, any code within such secondary main methods will be ignored. More robust support for automation of unit testing is provided by the JUnit framework, which is not part of the standard Java toolkit but freely available at www.junit.org. This framework allows the grouping of individual test cases into larger test suites, and provides support for executing those suites, and reporting or analyzing the results of those tests. As software is maintained, regression testing should be performed, whereby automation is used to re-execute all previous tests to ensure that changes to the software do not introduce new bugs in previously tested components. Debugging The simplest debugging technique consists of using print statements to track the values of variables during the execution of the program. A problem with this ap- proach is that eventually the print statements need to be removed or commented out, so they are not executed when the software is finally released. A better approach is to run the program within a debugger, which is a special- ized environment for controlling and monitoring the execution of a program. The basic functionality provided by a debugger is the insertion of breakpoints within the code. When the program is executed within the debugger, it stops at each breakpoint. While the program is stopped, the current value of variables can be inspected. In addition to fixed breakpoints, advanced debuggers allow specifica- tion of conditional breakpoints, which are triggered only if a given expression is satisfied. The standard Java toolkit includes a basic debugger named jdb, which has a command-line interface. Most IDEs for Java programming provide advanced debugging environments with graphical user interfaces. www.it-ebooks.info 1.10. Exercises 55 1.10 Exercises Reinforcement R-1.1 Write a short Java method, inputAllBaseTypes, that inputs a different value of each base type from the standard input device and prints it back to the standard output device. R-1.2 Suppose that we create an array A of GameEntry objects, which has an integer scores field, and we clone A and store the result in an array B. If we then im- mediately set A.score equal to 550, what is the score value of the GameEntry object referenced by B? R-1.3 Write a short Java method, isMultiple, that takes two long values, n and m, and returns true if and only if n is a multiple of m, that is, n = mi for some integer i. R-1.4 Write a short Java method, isEven, that takes an int i and returns true if and only if i is even. Your method cannot use the multiplication, modulus, or division operators, however. R-1.5 Write a short Java method that takes an integer n and returns the sum of all positive integers less than or equal to n. R-1.6 Write a short Java method that takes an integer n and returns the sum of all the odd positive integers less than or equal to n. R-1.7 Write a short Java method that takes an integer n and returns the sum of the squares of all positive integers less than or equal to n. R-1.8 Write a short Java method that counts the number of vowels in a given character string. R-1.9 Write a short Java method that uses a StringBuilder instance to remove all the punctuation from a string s storing a sentence, for example, transforming the string "Let’s try, Mike!" to "Lets try Mike". R-1.10 Write a Java class, Flower, that has three instance variables of type String, int, and float, which respectively represent the name of the flower, its number of petals, and price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and getting the value of each type. R-1.11 Modify the CreditCard class from Code Fragment 1.5 to include a method that updates the credit limit. R-1.12 Modify the CreditCard class from Code Fragment 1.5 so that it ignores any re- quest to process a negative payment amount. R-1.13 Modify the declaration of the first for loop in the main method in Code Frag- ment 1.6 so that its charges will cause exactly one of the three credit cards to attempt to go over its credit limit. Which credit card is it? www.it-ebooks.info 56 Chapter 1. Java Primer Creativity C-1.14 Write a pseudocode description of a method that reverses an array of n integers, so that the numbers are listed in the opposite order than they were before, and compare this method to an equivalent Java method for doing the same thing. C-1.15 Write a pseudocode description of a method for finding the smallest and largest numbers in an array of integers and compare that to a Java method that would do the same thing. C-1.16 Write a short program that takes as input three integers, a, b, and c, from the Java console and determines if they can be used in a correct arithmetic formula (in the given order), like “a + b = c,” “a = b − c,” or “a ∗ b = c.” C-1.17 Write a short Java method that takes an array of int values and determines if there is a pair of distinct elements of the array whose product is even. C-1.18 The p-norm of a vector v = (v1 , v2 ,... , vn ) in n-dimensional space is defined as q p p kvk = v1 + v2p + · · · + vnp. For the special case of p = 2, this results in the traditional Euclidean norm, which represents the length of the vector. For example, the Euclidean norm of a two-dimensional √ √ vector √ with coordinates (4, 3) has a Euclidean norm of 42 + 32 = 16 + 9 = 25 = 5. Give an implementation of a method named norm such that norm(v, p) returns the p-norm value of v and norm(v) returns the Euclidean norm of v, where v is represented as an array of coordinates. C-1.19 Write a Java program that can take a positive integer greater than 2 as input and write out the number of times one must repeatedly divide this number by 2 before getting a value less than 2. C-1.20 Write a Java method that takes an array of float values and determines if all the numbers are different from each other (that is, they are distinct). C-1.21 Write a Java method that takes an array containing the set of all integers in the range 1 to 52 and shuffles it into random order. Your method should output each possible order with equal probability. C-1.22 Write a short Java program that outputs all possible strings formed by using the characters 'c', 'a', 't', 'd', 'o', and 'g' exactly once. C-1.23 Write a short Java program that takes two arrays a and b of length n storing int values, and returns the dot product of a and b. That is, it returns an array c of length n such that c[i] = a[i] · b[i], for i = 0,... , n − 1. C-1.24 Modify the CreditCard class from Code Fragment 1.5 so that printSummary be- comes a nonstatic method, and modify the main method from Code Fragment 1.6 accordingly. C-1.25 Modify the CreditCard class to add a toString( ) method that returns a String representation of the card (rather than printing it to the console, as done by printSummary). Modify the main method from Code Fragment 1.6 accordingly to use the standard println command. www.it-ebooks.info Chapter Notes 57 Projects P-1.26 Write a short Java program that takes all the lines input to standard input and writes them to standard output in reverse order. That is, each line is output in the correct order, but the ordering of the lines is reversed. P-1.27 Write a Java program that can simulate a simple calculator, using the Java console as the exclusive input and output device. That is, each input to the calculator, be it a number, like 12.34 or 1034, or an operator, like + or =, can be done on a separate line. After each such input, you should output to the Java console what would be displayed on your calculator. P-1.28 A common punishment for school children is to write out a sentence multiple times. Write a Java stand-alone program that will write out the following sen- tence one hundred times: “I will never spam my friends again.” Your program should number each of the sentences and it should make eight different random- looking typos. P-1.29 The birthday paradox says that the probability that two people in a room will have the same birthday is more than half, provided n, the number of people in the room, is more than 23. This property is not really a paradox, but many people find it surprising. Design a Java program that can test this paradox by a series of experiments on randomly generated birthdays, which test this paradox for n = 5, 10, 15, 20,..., 100. P-1.30 (For those who know Java graphical user interface methods:) Define a Graphi- calTest class that tests the functionality of the CreditCard class from Code Frag- ment 1.5 using text fields and buttons. Chapter Notes For more detailed information about the Java programming language, we refer the reader to the Java website (http://www.java.com), as well as some of the fine books about Java, including the books by Arnold, Gosling and Holmes , Flanagan , and Horstmann and Cornell [47, 48]. www.it-ebooks.info www.it-ebooks.info Chapter 2 Object-Oriented Design Contents 2.1 Goals, Principles, and Patterns................ 60 2.1.1 Object-Oriented Design Goals............... 60 2.1.2 Object-Oriented Design Principles............. 61 2.1.3 Design Patterns....................... 63 2.2 Inheritance........................... 64 2.2.1 Extending the CreditCard Class............... 65 2.2.2 Polymorphism and Dynamic Dispatch........... 68 2.2.3 Inheritance Hierarchies................... 69 2.3 Interfaces and Abstract Classes............... 76 2.3.1 Interfaces in Java...................... 76 2.3.2 Multiple Inheritance for Interfaces............. 79 2.3.3 Abstract Classes....................... 80 2.4 Exceptions........................... 82 2.4.1 Catching Exceptions..................... 82 2.4.2 Throwing Exceptions.................... 85 2.4.3 Java’s Exception Hierarchy................. 86 2.5 Casting and Generics..................... 88 2.5.1 Casting........................... 88 2.5.2 Generics........................... 91 2.6 Nested Classes......................... 96 2.7 Exercises............................ 97 www.it-ebooks.info 60 Chapter 2. Object-Oriented Design 2.1 Goals, Principles, and Patterns As the name implies, the main “actors” in the object-oriented paradigm are called objects. Each object is an instance of a class. Each class presents to the outside world a concise and consistent view of the objects that are instances of this class, without going into too much unnecessary detail or giving others access to the inner workings of the objects. The class definition typically specifies the data fields, also known as instance variables, that an object contains, as well as the methods (operations) that an object can execute. This view of computing fulfill several goals and incorporates design principles, which we will discuss in this chapter. 2.1.1 Object-Oriented Design Goals Software implementations should achieve robustness, adaptability, and reusabil- ity. (See Figure 2.1.) Figure 2.1: Goals of object-oriented design. Robustness Every good programmer wants to develop software that is correct, which means that a program produces the right output for all the anticipated inputs in the program’s application. In addition, we want software to be robust, that is, capable of handling unexpected inputs that are not explicitly defined for its application. For example, if a program is expecting a positive integer (perhaps representing the price of an item) and instead is given a negative integer, then the program should be able to recover gracefully from this error. More importantly, in life-critical applications, where a software error can lead to injury or loss of life, software that is not robust could be deadly. This point was driven home in the late 1980s in accidents involv- ing Therac-25, a radiation-therapy machine, which severely overdosed six patients between 1985 and 1987, some of whom died from complications resulting from their radiation overdose. All six accidents were traced to software errors. www.it-ebooks.info 2.1. Goals, Principles, and Patterns 61 Adaptability Modern software applications, such as Web browsers and Internet search engines, typically involve large programs that are used for many years. Software, there- fore, needs to be able to evolve over time in response to changing conditions in its environment. Thus, another important goal of quality software is that it achieves adaptability (also called evolvability). Related to this concept is portability, which is the ability of software to run with minimal change on different hardware and operating system platforms. An advantage of writing software in Java is the porta- bility provided by the language itself. Reusability Going hand in hand with adaptability is the desire that software be reusable, that is, the same code should be usable as a component of different systems in various applications. Developing quality software can be an expensive enterprise, and its cost can be offset somewhat if the software is designed in a way that makes it easily reusable in future applications. Such reuse should be done with care, however, for one of the major sources of software errors in the Therac-25 came from inappropri- ate reuse of Therac-20 software (which was not object-oriented and not designed for the hardware platform used with the Therac-25). 2.1.2 Object-Oriented Design Principles Chief among the principles of the object-oriented approach, which are intended to facilitate the goals outlined above, are the following (see Figure 2.2): Abstraction Encapsulation Modularity Abstraction Encapsulation Modularity Figure 2.2: Principles of object-oriented design. www.it-ebooks.info 62 Chapter 2. Object-Oriented Design Abstraction The notion of abstraction is to distill a complicated system down to its most funda- mental parts. Typically, describing the parts of a system involves naming them and explaining their functionality. Applying the abstraction paradigm to the design of data structures gives rise to abstract data types (ADTs). An ADT is a mathematical model of a data structure that specifies the type of data stored, the operations sup- ported on them, and the types of parameters of the operations. An ADT specifies what each operation does, but not how it does it. In Java, an ADT can be expressed by an interface, which is simply a list of method declarations, where each method has an empty body. (We will say more about Java interfaces in Section 2.3.1.) An ADT is realized by a concrete data structure, which is modeled in Java by a class. A class defines the data being stored and the operations supported by the objects that are instances of the class. Also, unlike interfaces, classes specify how the operations are performed in the body of each method. A Java class is said to implement an interface if its methods include all the methods declared in the interface, thus providing a body for them. However, a class can have more methods than those of the interface. Encapsulation Another important principle of object-oriented design is encapsulation; different components of a software system should not reveal the internal details of their respective implementations. One of the main advantages of encapsulation is that it gives one programmer freedom to implement the details of a component, without concern that other programmers will be writing code that intricately depends on those internal decisions. The only constraint on the programmer of a component is to maintain the public interface for the component, as other programmers will be writing code that depends on that interface. Encapsulation yields robustness and adaptability, for it allows the implementation details of parts of a program to change without adversely affecting other parts, thereby making it easier to fix bugs or add new functionality with relatively local changes to a component. Modularity Modern software systems typically consist of several different components that must interact correctly in order for the entire system to work properly. Keeping these interactions straight requires that these different components be well orga- nized. Modularity refers to an organizing principle in which different compo- nents of a software system are divided into separate functional units. Robustness is greatly increased because it is easier to test and debug separate components before they are integrated into a larger software system. www.it-ebooks.info 2.1. Goals, Principles, and Patterns 63 2.1.3 Design Patterns Object-oriented design facilitates reusable, robust, and adaptable software. De- signing good code takes more than simply understanding object-oriented method- ologies, however. It requires the effective use of object-oriented design techniques. Computing researchers and practitioners have developed a variety of organiza- tional concepts and methodologies for designing quality object-oriented software that is concise, correct, and reusable. Of special relevance to this book is the con- cept of a design pattern, which describes a solution to a “typical” software design problem. A pattern provides a general template for a solution that can be applied in many different situations. It describes the main elements of a solution in an abstract way that can be specialized for a specific problem at hand. It consists of a name, which identifies the pattern; a context, which describes the scenarios for which this pattern can be applied; a template, which describes how the pattern is applied; and a result, which describes and analyzes what the pattern produces. We present several design patterns in this book, and we show how they can be consistently applied to implementations of data structures and algorithms. These design patterns fall into two groups—patterns for solving algorithm design prob- lems and patterns for solving software engineering problems. Some of the algo- rithm design patterns we discuss include the following: Recursion (Chapter 5) Amortization (Sections 7.2.3, 11.4.4, and 14.7.3) Divide-and-conquer (Section 12.1.1) Prune-and-search, also known as decrease-and-conquer (Section 12.5.1) Brute force (Section 13.2.1) The greedy method (Sections 13.4.2, 14.6.2, and 14.7) Dynamic programming (Section 13.5) Likewise, some of the software engineering design patterns we discuss include: Template method (Sections 2.3.3, 10.5.1, and 11.2.1) Composition (Sections 2.5.2, 2.6, and 9.2.1) Adapter (Section 6.1.3) Position (Sections 7.3, 8.1.2, and 14.7.3) Iterator (Section 7.4) Factory Method (Sections 8.3.1 and 11.2.1) Comparator (Sections 9.2.2, 10.3, and Chapter 12) Locator (Section 9.5.1) Rather than explain each of these concepts here, however, we will introduce them throughout the text as noted above. For each pattern, be it for algorithm engineering or software engineering, we explain its general use and we illustrate it with at least one concrete example. www.it-ebooks.info 64 Chapter 2. Object-Oriented Design 2.2 Inheritance A natural way to organize various structural components of a software package is in a hierarchical fashion, with similar abstract definitions grouped together in a level-by-level manner that goes from specific to more general as one traverses up the hierarchy. An example of such a hierarchy is shown in Figure 2.3. Using mathematical notations, the set of houses is a subset of the set of buildings, but a superset of the set of ranches. The correspondence between levels is often referred to as an “is a” relationship, as a house is a building, and a ranch is a house. Building Apartment House Commercial Building Low-rise High-rise Two-story Ranch Skyscraper Apartment Apartment House Figure 2.3: An example of an “is a” hierarchy involving architectural buildings. A hierarchical design is useful in software development, as common function- ality can be grouped at the most general level, thereby promoting reuse of code, while differentiated behaviors can be viewed as extensions of the general case. In object-oriented programming, the mechanism for a modular and hierarchical orga- nization is a technique known as inheritance. This allows a new class to be defined based upon an existing class as the starting point. In object-oriented terminology, the existing class is typically described as the base class, parent class, or super- class, while the newly defined class is known as the subclass or child class. We say that the subclass extends the superclass. When inheritance is used, the subclass automatically inherits, as its starting point, all methods from the superclass (other than constructors). The subclass can differentiate itself from its superclass in two ways. It may augment the superclass by adding new fields and new methods. It may also specialize existing behaviors by providing a new implementation that overrides an existing method. www.it-ebooks.info 2.2. Inheritance 65 2.2.1 Extending the CreditCard Class As an introduction to the use of inheritance, we revisit the CreditCard class of Section 1.7, designing a new subclass that, for lack of a better name, we name PredatoryCreditCard. The new class will differ from the original in two ways: (1) if an attempted charge is rejected because it would have exceeded the credit limit, a $5 fee will be charged, and (2) there will be a mechanism for assessing a monthly interest charge on the outstanding balance, using an annual percentage rate (APR) specified as a constructor parameter. Figure 2.4 provides a UML diagram that serves as an overview of our design for the new PredatoryCreditCard class as a subclass of the existing CreditCard class. The hollow arrow in that diagram indicates the use of inheritance, with the arrow oriented from the subclass to the superclass. The PredatoryCreditCard class augments the original CreditCard class, adding a new instance variable named apr to store the annual percentage rate, and adding a new method named processMonth that will assess interest charges. The new class also specializes its superclass by overriding the original charge method in order to provide a new implementation that assess a $5 fee for an attempted overcharge. class: CreditCard fields: − customer : String − limit : int − bank : String # balance : double − account : String methods: + getCustomer( ) : String + getAccount( ) : String + getBank( ) : String + getLimit( ) : int + charge(price : double) : boolean + getBalance( ) : double + makePayment(amount : double) class: PredatoryCreditCard fields: − apr : double methods: + charge(price : double) : boolean + processMonth( ) Figure 2.4: A UML diagram showing PredatoryCreditCard as a subclass of CreditCard. (See Figure 1.5 for the original CreditCard design.) www.it-ebooks.info 66 Chapter 2. Object-Oriented Design To demonstrate the mechanisms for inheritance in Java, Code Fragment 2.1 presents a complete implementation of the new PredatoryCreditCard class. We wish to draw attention to several aspects of the Java implementation. We begin with the first line of the class definition, which indicates that the new class inherits from the existing CreditCard class by using Java’s extends keyword followed by the name of its superclass. In Java, each class can extend exactly one other class. Because of this property, Java is said to allow only single inheritance among classes. We should also note that even if a class definition makes no explicit use of the extends clause, it automatically inherits from a class, java.lang.Object, which serves as the universal superclass in Java. We next consider the declaration of the new apr instance variable, at line 3 of the code. Each instance of the PredatoryCreditCard class will store each of the variables inherited from the CreditCard definition (customer, bank, account, limit, and balance) in addition to the new apr variable. Yet we are only responsible for declaring the new instance variable within the subclass definition. 1 public class PredatoryCreditCard extends CreditCard { 2 // Additional instance variable 3 private double apr; // annual percentage rate 4 5 // Constructor for this class 6 public PredatoryCreditCard(String cust, String bk, String acnt, int lim, 7 double initialBal, double rate) { 8 super(cust, bk, acnt, lim, initialBal); // initialize superclass attributes 9 apr = rate; 10 } 11 12 // A new method for assessing monthly interest charges 13 public void processMonth( ) { 14 if (balance > 0) { // only charge interest on a positive balance 15 double monthlyFactor = Math.pow(1 + apr, 1.0/12); // compute monthly rate 16 balance ∗= monthlyFactor; // assess interest 17 } 18 } 19 20 // Overriding the charge method defined in the superclass 21 public boolean charge(double price) { 22 boolean isSuccess = super.charge(price); // call inherited method 23 if (!isSuccess) 24 balance += 5; // assess a $5 penalty 25 return isSuccess; 26 } 27 } Code Fragment 2.1: A subclass of CreditCard that assesses interest and fees. www.it-ebooks.info 2.2. Inheritance 67 Constructors are never inherited in Java. Lines 6–10 of Code Fragment 2.1 define a constructor for the new class. When a PredatoryCreditCard instance is created, all of its fields must be properly initialized, including any inherited fields. For this reason, the first operation performed within the body of a constructor must be to invoke a constructor of the superclass, which is responsible for properly ini- tializing the fields defined in the superclass. In Java, a constructor of the superclass is invoked by using the keyword super with appropriate parameterization, as demonstrated at line 8 of our implementation: super(cust, mk, acnt, lim, initialBal); This use of the super keyword is very similar to use of the keyword this when invoking a different constructor within the same class (as described on page 15 of Section 1.2.2). If a constructor for a subclass does not make an explicit call to super or this as its first command, then an implicit call to super( ), the zero-parameter version of the superclass constructor, will be made. Returning our attention to the constructor for PredatoryCreditCard, after calling the superclass constructor with appropriate parameters, line 9 initializes the newly declared apr field. (That field was unknown to the superclass.) The processMonth method is a new behavior, so there is no inherited version upon which to rely. In our model, this method should be invoked by the bank, once each month, to add new interest charges to the customer’s balance. From a technical aspect, we note that this method accesses the value of the inherited balance field (at line 14), and potentially modifies that balance at line 16. This is permitted precisely because the balance attributed was declared with protected visibility in the original CreditCard class. (See Code Fragment 1.5.) The most challenging aspect in implementing the processMonth method is making sure we have working knowledge of how an annual percentage rate trans- lates to a monthly rate. We do not simply divide the annual rate by twelve to get a monthly rate (that would be too predatory, as it would result in a higher APR than advertised). The correct computation is to take the twelfth-root of 1 + apr, and use that as a multiplicative √ factor. For example, if the APR is 0.0825 (representing 8.25%), we compute 12 1.0825 ≈ 1.006628, and therefore charge 0.6628% interest per month. In this way, each $100 of debt will amass $8.25 of compounded interest in a year. Notice that we use the Math.pow method from Java’s libraries. Finally, we consider the new implementation of the charge method provided for the PredatoryCreditCard class (lines 21–27). This definition overrides the inherited method. Yet, our implementation of the new method relies on a call to the inherited method, with syntax super.charge(price) at line 22. The return value of that call designates whether the charge was successful. We examine that return value to decide whether to assess a fee, and in either case return that boolean to the caller, so that the new version of charge maintains a similar outward interface as the original. www.it-ebooks.info 68 Chapter 2. Object-Oriented Design 2.2.2 Polymorphism and Dynamic Dispatch The word polymorphism literally means “many forms.” In the context of object- oriented design, it refers to the ability of a reference variable to take different forms. Consider, for example, the declaration of a variable having CreditCard as its type: CreditCard card; Because this is a reference variable, the statement declares the new variable, which does not yet refer to any card instance. While we have already seen that we can assign it to a newly constructed instance of the CreditCard class, Java also allows us to assign that variable to refer to an instance of the PredatoryCreditCard subclass. That is, we can do the following: CreditCard card = new PredatoryCreditCard(...); // parameters omitted This is a demonstration of what is known as the Liskov Substitution Principle, which states that a variable (or parameter) with a declared type can be assigned an instance from any direct or indirect subclass of that type. Informally, this is a manifestation of the “is a” relationship modeled by inheritance, as a predatory credit card is a credit card (but a credit card is not necessarily predatory). We say that the variable, card, is polymorphic; it may take one of many forms, depending on the specific class of the object to which it refers. Because card has been declared with type CreditCard, that variable may only be used to call methods that are declared as part of the CreditCard definition. So we can call card.makePayment(50) and card.charge(100), but a compilation error would be reported for the call card.processMonth( ) because a CreditCard is not guaranteed to have such a behavior. (That call could be made if the variable were originally declared to have PredatoryCreditCard as its type.) An interesting (and important) issue is how Java handles a call such as card.charge(100) when the variable card has a declared type of CreditCard. Recall that the object referenced by card might be an instance of the CreditCard class or an instance of the PredatoryCreditCard class, and that there are distinct implemen- tations of the charge method: CreditCard.charge and PredatoryCreditCard.charge. Java uses a process known as dynamic dispatch, deciding at runtime to call the ver- sion of the method that is most specific to the actual type of the referenced object (not the declared type). So, if the object is a PredatoryCreditCard instance, it will execute the PredatoryCreditCard.charge method, even if the reference variable has a declared type of CreditCard. Java also provides an instanceof operator that tests, at runtime, whether an in- stance satisfies as a particular type. For example, the evaluation of the boolean con- dition, (card instanceof PredatoryCreditCard), produces true if the object cur- rently referenced by the variable card belongs to the PredatoryCreditCard class, or any further subclass of that class. (See Section 2.5.1 for further discusion.) www.it-ebooks.info 2.2. Inheritance 69 2.2.3 Inheritance Hierarchies Although a subclass may not inherit from multiple superclasses in Java, a superclass may have many subclasses. In fact, it is quite common in Java to develop complex inheritance hierarchies to maximize the reusability of code. As a second example of the use of inheritance, we develop a hierarchy of classes for iterating numeric progressions. A numeric progression is a sequence of num- bers, where each number depends on one or more of the previous numbers. For example, an arith