PREFACE

This book is intended for an object-oriented course in data structures and algorithms. The implementation language is Java, and it is assumed that students have taken a first course in programming, not necessarily in Java. That course should have covered the fundamental statements and data types, as well as arrays. Chapter 0 supplies the material on Java that is fundamental to the remaining chapters, so it serves as a review for those with previous experience in Java, and brings Java novices up to speed.

WHAT'S NEW IN THE THIRD EDITION

This edition presents two major changes from the second edition. First, the Scanner class has replaced the BufferedReader and StringTokenizer classes. The Scanner class's versatility supports pattern matching as well as keyboard input and file input. Second, there is an increased emphasis on testing. In particular, the unit-testing features of JUnit 4 are introduced in Chapter 2 and integrated in applications throughout the remaining chapters.

THE JAVA COLLECTIONS FRAMEWORK

One of the distinctive features of this text is its emphasis on the Java Collections Framework, part of the java.utii package. Basically, the framework is a hierarchy with interfaces at each level except the lowest, and collection classes that implement those interfaces at the lowest level. The collection classes implement most of the data structures studied in a second computer-science course, such as a resizable array class, a linked-list class, a stack class, a queue class, a balanced binary-search-tree class, a priority-queue class, and a hash-map class.

There are several advantages to using the Java Collections Framework. First, students will be working with code that has been extensively tested; they need not depend on modules created by the instructor or textbook author. Second, the framework is available for later courses in the curriculum and beyond. Third, although the primary emphasis is on using the Java Collections Framework, the framework classes are not treated simply as "black boxes." For each such class, the heading and fields are provided, and one method definition is dissected. This exposition takes away some of the mystery that would otherwise surround the class, and allows students to see the efficiency and succinctness of professionals' code.

The version of the Java Collections Framework we will be working with includes type parameters. Type parameters, sometimes called "generic types," "generics," or "templates," were added to the Java language starting with Java 5.0. With type parameters, there is no need to downcast the return value from a collection, and many errors can be detected at compile-time that previously were discoverable only at run-time.

To complement generics, three other features have been added: boxing, unboxing, and an enhanced for statement. The elements in generic collections must be objects, often from a wrapper class such as Integer. If a primitive value appears where a collection method requires a wrapper element as an argument, boxing automatically converts the primitive value to the corresponding wrapper element. Conversely, if a wrapper-class element appears where a primitive value is needed, unboxing automatically converts that element to the corresponding primitive value. Finally, the enhanced for statement—often called a "for-each" statement—has a sleek structure for iterating through a collection. The net effect of these new features of Java is to improve productivity by relegating to the compiler many of the "boiler-plate" details related to casting and iterating.

OTHER IMPLEMENTATIONS CONSIDERED

As important as the Java Collections Framework implementations are, they cannot be the exclusive focus of such a fundamental course in data structures and algorithms. Approaches that differ from those in the framework deserve consideration. For example, the HashMap class utilizes chaining, so there is a separate section on open addressing, and a discussion of the trade-offs of one design over the other. Also, there is coverage of data structures (such as a weighted digraph class) and algorithms (such as Heap Sort) that are not yet included in the Java Collections Framework.

Sometimes, the complexity of the framework classes is mitigated by first introducing simpler versions of those classes. For example, the SingiyLinkedList class—not in the Java Collections Framework—helps to pave the way for the more powerful LinkedList class, which is in the framework. And the BinarySearchTree class prepares students to understand the framework's TreeMap class, based on red-black trees.

This text satisfies another important goal of a data structures and algorithms course: Students have the opportunity to develop their own data structures. There are programming projects in which data structures are either created "from the ground up" or extended from examples in the chapters. And there are many other projects to develop or extend applications that use the Java Collections Framework.

JUNIT AND TEST-FIRST DEVELOPMENT

Students realize that methods with no compile-time errors may still be a long way from correct, but they often need help in learning how to systematically test their methods. As described in Chapter 2, JUnit is an Open Source platform for the testing of units, that is, methods. For example, to test a findMedian method, a FindMedianTest class is developed. The FindMedianTest class consists mainly of methods that test findMedian. When all the test methods in FindMedianTest have been passed, the student's confidence in the correctness of findMedian is increased.

Instead of writing the tests after a method has been defined, we employ a "test-first" strategy. As soon as a method's specifications have been written, the tests for that method are coded. This ensures that the tests are based on the specifications only, not on the definition of the method. These tests are run on a "stub" version of the method to be tested, and all of the tests will fail. Then the method definition is written, and the tests are run on that version of the method. Corrections to the method are made as necessary until, eventually, all tests succeed. The test-first paradigm is introduced in Chapter 2 and utilized in subsequent chapters.

PEDAGOGICAL FEATURES

This text offers several features that may improve the teaching environment for instructors and the learning environment for students. Each chapter starts with a list of objectives, and most chapters conclude with several major programming assignments. Each chapter also has a crossword puzzle, from Crossword Weaver—to help students learn the key words and phrases in an enjoyable setting—and a variety of exercises. The answers to all of the exercises are available to the instructor.

Each data structure is carefully described, with the specifications for each method given in javadoc notation. Also, there are examples of how to call the method, and the results of that call. To reinforce the important aspects of the material and to hone students' coding skills in preparation for programming projects, there is a suite of 23 lab experiments. The organization of these labs is described later in this preface.

SUPPORT MATERIAL

The website for all of the support material is www.wiley.com/college/collins/

That website has links to the following information for students:

• The suite of 23 labs. Lab 0 starts with a brief overview of the lab format.
• The source codes for all classes developed in the text.
• Applets for projects that have a strong visual component.

Additionally, instructors can obtain the following from the website:

• PowerPoint slides for each chapter (approximately 1500 slides).
• Answers to every exercise and lab experiment.

SYNOPSES OF THE CHAPTERS

Chapter 0 serves as an introduction to the Java language for those whose first course was in some other language. For students who are already familiar with Java, the chapter consists mostly of review material, but the treatment of the Scanner class is worth perusing.

Chapter 1 focuses on the fundamentals of object-oriented programming: encapsulation, inheritance and polymorphism. For a concrete illustration of these topics, an interface is created and implemented, and the implementation is extended. The relationship between abstract data types and interfaces is explored, as is the corresponding connection between data structures and classes. The Universal Modeling Language provides a design tool to depict the interrelationships among interfaces, classes and subclasses.

Chapter 2 introduces unit testing with the free package JUnit. This is a vital topic in programming, so method testing—before the method is defined—is emphasized in virtually all subsequent applications, programming assignments and lab experiments. The chapter also includes some additional features of the Java language. For example, there are sections on exception handling, file output, and the Java Virtual Machine. Also, there is a section on the Object class's equals method, why that method should be overridden, and how to accomplish the overriding.

Finally, Chapter 2 introduces a "theme" project: to develop an integrated web browser and search engine. This project, based on a paper by Newhall and Meeden [2002], continues through six of the remaining chapters, and clearly illustrates the practical value of understanding data structures. In the first part of the project, students develop a graphical user interface—a version of this interface is available to instructors who prefer to provide this part of the project to students. The remaining six parts involve an ArrayList object, a LinkedList object, a TreeMap object, a PriorityQueue object, a HashMap object, and a Digraph object.

Chapter 3, Analysis of Algorithms, starts by defining functions to estimate a method's execution-time requirements, both in the average and worst cases. Big-O notation provides a convenient tool for estimating these estimates. Because Big-O notation yields environment-independent estimates, these results are then compared with actual run-times, which are determined with the help of the Random class and the nanoTime method.

Chapter 4 outlines the Java Collections Framework. We start with some preliminary material on collection classes in general, type parameters and the iterator design-pattern. The remainder of the chapter presents part of the major interface hierarchy (Collection and List) and its implementations (ArrayList and LinkedList).

Chapter 5, on recursion, represents a temporary shift in emphasis from data structures to algorithms. There is a gradual progression from simple examples (factorial and decimal-to-binary) to more powerful examples (binary search and backtracking). The mechanism for illustrating the execution of recursive methods is the execution frame. Backtracking is introduced, not only as a design pattern, but as another illustration of creating polymorphic references through interfaces. And the same BackTrack class is used for maze-searching and solving eight queens, knight's tour, Sudoku, and Numbrix.

In Chapter 6, we study the Java Collections Framework's ArrayList class. An ArrayList object is a smart array: automatically resizable, and with methods to handle insertions and deletions at any index. The design starts with the method specifications for some of the most widely-used methods in the ArrayList class. There follows a brief outline of the implementation of the class. The application of the ArrayList class, high-precision arithmetic, is essential for public-key cryptography. This application is extended in a lab and in a programming project. Several JUnit 4 tests are included in the chapter, and the remaining tests are available from the book's website.

Chapter 7 presents linked lists. A discussion of singly-linked lists leads to the development of a primitive SinglyLinkedList class. This serves mainly to prepare students for the framework's LinkedList class. LinkedList objects are characterized by linear-time methods for inserting, removing or retrieving at an arbitrary position. This property makes a compelling case for list iterators: objects that traverse a LinkedList object and have constant-time methods for inserting, removing or retrieving at the "current" position. The framework's design is doubly-linked and circular, but other approaches are also considered. The application is a small line-editor, for which list iterators are well suited. Testing entails an interesting feature: the testing of protected methods. The line-editor application is extended in a programming project.

Stacks and queues are the subjects of Chapter 8. The framework's Stack class has the expected push, pop, and peek methods. But the Stack class also allows elements to be inserted or removed anywhere in a Stack object, and this permission violates the definition. Students can use the Stack class—with care—or develop their own version that satisfies the definition of a stack. There are two applications of stacks: the implementation of recursion by a compiler, and the conversion from infix to postfix. This latter application is expanded in a lab, and forms the basis for a project on evaluating a condition.

The Java Collections Framework has a Queue interface, but that interface supports the removal of any element from a queue! As with the Stack class, students can tolerate this flaw and use a class—such as LinkedList —that implements the Queue interface. Or they can create their own implementation that does not violate the definition of a queue. The specific application of queues, calculating the average waiting time at a car wash, falls into the general category of computer simulation.

Chapter 9 focuses on binary trees in general, as a prelude to the material in Chapters 10 through 13. The essential features of binary trees are presented, including both botanical (root, branch, leaf) and familial (parent, child, sibling) terms. Binary trees are important for understanding later material on AVL trees, decision trees, red-black trees, heaps, and Huffman trees.

In Chapter 10, we look at binary search trees, including a BinarySearchTree class, and explain the value of balanced binary search trees. Rotations are introduced as the mechanism by which re-balancing is accomplished, and AVL trees are offered as examples of balanced binary search trees. An AVLTree class, as a subclass of BinarySearchTree, is outlined; the crucial methods, fixAfterInsertion and fixAfterDeletion, are left as programming projects.

Sorting is the theme of Chapter 11. Estimates of the lower bounds for comparison-based sorts are determined. A few simple sorts are defined, and then we move on to two sort methods provided by the framework. Quick Sort sorts an array of a primitive type, and Merge Sort works for an array of objects and for implementations of the List interface. A lab experiment compares all of these sort algorithms on randomly-generated integers.

The central topic of Chapter 12 is how to use the TreeMap class. A map is a collection in which each element has a unique key part and also a value part. In the TreeMap implementation of the Map interface, the elements are stored in a red-black tree, ordered by the elements' keys. There are labs to guide students through the details of re-structuring after an insertion or removal. The application consists of searching a thesaurus for synonyms, and JUnit 4 testing is again illustrated. The TreeSet class has a TreeMap field in which each element has the same, dummy value-part. The application of the TreeSet class is a simple spell-checker, which is also thoroughly tested.

Chapter 13 introduces the PriorityQueue class. This class is part of the Java Collections Framework and, like the Stack class and Queue interface in Chapter 8, allows methods that violate the definition of a priority queue. The class utilizes a heap to provide insertions in constant average time, and removal of the smallest-valued element in logarithmic worst time. The application is in the area of data compression: Given a text file, generate a minimal, prefix-free encoding. There is a project assignment to convert the encoded message back to the original text file.

Chapter 14 investigates hashing. The Java Collections Framework has a HashMap class for elements that consist of unique-key/value pairs. Basically, the average time for insertion, removal, and searching is constant! This average speed is exploited in an application (and JUnit 4 tests) to create a simple symbol table. The Java Collections Framework's implementation of hashing, using chained hashing, is compared to open-address hashing.

The most general data structures—graphs, trees, and networks—are presented in Chapter 15. There are outlines of the essential algorithms: breadth-first traversal, depth-first traversal, finding a minimum spanning tree, and finding the shortest or longest path between two vertices. The only class developed is the (directed) Network class, with an adjacency-map implementation. Other classes, such as UndirectedGraph and UndirectedNetwork, can be straightforwardly defined as subclasses of Network. The Traveling Salesperson Problem is investigated in a lab, and there is a programming project to solve that problem—not necessarily in polynomial time! Another backtracking application is presented, with the same BackTrack class that was introduced in Chapter 5.

The website includes all programs developed in each chapter, all JUnit 4 tests, and applets, where appropriate, to animate the concepts presented.

APPENDIXES

Appendix 1 has two additional features of the Java Collections Framework. Each of the collection classes in the framework is serializable, that is, an instance of the class can be conveniently stored to an output stream, and the instance can later be re-constituted from an input stream (de-serialization). Framework iterators are fail-fast: During an iteration through a collection, there should be no insertions into or removals from the collection except by the iterator. Otherwise, the integrity of that iterator may be compromised, so an exception will be thrown as soon as the iterator's unreliability has been established.

Appendix 2 contains the background that will allow students to comprehend the mathematical aspects of the chapters. Summation notation and the rudimentary properties of logarithms are essential, and the material on mathematical induction will lead to a deeper appreciation of recursion as well as the analysis of binary trees.

Appendix 3, "Choosing a Data Structure," can be viewed as a summary of the eight major data structures in the book. These collection classes are categorized according to their ordering of elements (for example, time-based for stacks and queues) and according to their performance of standard operations (for example, the TreeMap class requires logarithmic-in-n time to search for a key). Table A3.1 summarizes the summary.

ORGANIZATION OF THE LABS

There are 23 web labs associated with this text. For both students and instructors, the initial Uniform Resource Locator (URL) is www.wiley.com/college/collins.

The labs do not contain essential material, but provide reinforcement of the text material. For example, after the ArrayList and LinkedList classes have been investigated, there is a lab to perform some timing experiments on those two classes.

The labs are self-contained, so the instructor has considerable flexibility in assigning the labs:

1. they can be assigned as closed labs;
2. they can be assigned as open labs;
3. they can be assigned as ungraded homework.

In addition to the obvious benefit of promoting active learning, these labs also encourage use of the scientific method. Basically, each lab is set up as an experiment. Students observe some phenomenon, such as creating a greedy cycle to solve the Traveling Salesperson Problem. They then formulate and submit a hypothesis—with their own code—about the phenomenon. After testing and, perhaps, revising their hypothesis, they submit the conclusions they drew from the experiment.

ACKNOWLEDGEMENTS

Joshua Bloch, lead designer of the Java Collections Framework, gave valuable insights on type parameters and their impact on the Java Collections Framework.

Chun Wai Liew of Lafayette College helped to incorporate JUnit into this edition of the text.

I am indebted to the suggestions and corrections of the reviewers: Dean Hendrix (Auburn University), Benjamin Kuperman (Oberlin College), Andrew Haas (State University of New York—Albany), Kathy Liszka (University of Akron), Paul Bladek (Edmonds Community College), Siva Jasthi (Metropolitan State University), Hashem Anwari (Northern Virginia Community College), Alan Peslak (Nova Southeastern University), H. K. Dai (Oklahoma State University), Jiang Li (Austin Peay State University), Paul J. Wagner (University of Wisconsin—Eau Claire), John Mallozzi (Iona College), Robert Goldberg (Queens College), and Michael Clancy (University of California—Berkeley).