Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

This version of the book has been translated to Java for use in the Data Structures course at Evergreen Valley College in San José, California. We hope it will be useful to you. This preface was written by J. David Eisenberg, based on (but not reviewed by) the book’s original authors.

Since you have started to read this book, we can only assume that you have an interest in computer science. You may also be interested in the programming language Java and have likely done some programming, either in an earlier computer science course or perhaps on your own. In any case, you are hoping to learn more.

This textbook is about computer science. It is also about Java. However, there is much more. The study of algorithms and data structures is central to understanding what computer science is all about.

Learning computer science is not unlike learning any other type of difficult subject matter. The only way to be successful is through deliberate and incremental exposure to the fundamental ideas. A beginning computer scientist needs practice so that there is a thorough understanding before continuing on to the more complex parts of the curriculum. In addition, a beginner needs to be given the opportunity to be successful and gain confidence.

This textbook is designed to serve as a text for a first course on data structures and algorithms, typically taught as the second course in the computer science curriculum. Even though the second course is considered more advanced than the first course, we still assume that you are beginners at this level. You may still be struggling with some of the basic ideas and skills from your first computer science course and yet you are ready to further explore the discipline and continue to practice problem solving.

As we said earlier, this book is about computer science. It is about abstract data types and data structures. It is also about writing algorithms and solving problems. In the following chapters, we will look at a number of data structures and solve classic problems that arise. The tools and techniques that you learn in these chapters will be applied over and over as you continue your study of computer science.

Many students discover at this point that there is much more to computer science than just writing programs. Data structures and algorithms can be studied and understood at a level that is independent of writing code.

We assume that students have had a traditional first course in computer science, preferably although not necessarily in Java. They understand basic programming constructs such as selection, iteration, and function definition. They have been exposed to object-oriented programming in that they can construct and use simple classes. Students also understand the basic Java data structures such as sequences (arrays and Strings).

We begin our study of data structures by considering the linear structures, in particular, stacks, queues, deques, and lists. Java ArrayLists as well as linked lists are used for implementation. We then transition to the nonlinear structures related to trees and introduce a number of techniques including linked node and reference architectures (linked lists). We conclude with graphs, using linked structures, lists, and Java HashMaps for implementation. In each case, we have strived to show a variety of implementation techniques. Though the Java Collections framework contains implementations of structures such as Stack, Deque, and Queue, we do not use them. Instead, we derive them from first principles with ArrayList as the underlying strcture.

We believe that it is advantageous for beginning students to spend time learning the rudimentary ideas relating to algorithms and data structures. We are using Java for this course because a large number of students at Evergreen Valley College transfer to universities where Java is used in the Computer Science curriculum. The choice of Java means that we have had to modify several things. First, some Python examples used lists of heterogeneous data (strings, floats, and booleans). In Java, collections must have the same data type (or subclasses of the data type). There is no “sum type” as in OCaml or Haskell, which would provide a capability for heterogeneous data.

Second, the introduction to Java is larger, as there are more concepts that students need to know. I have offloaded the longer discussion of object-oriented programming to Appendix A.

We have designed this textbook around problem solving using classic data structures and techniques. The organizational chart depicts possible ways to use the material.

Chapter 1 is intended to provide background material with a review of computer science, problem solving, object-oriented programming, and Java. It is very possible that well-prepared students can skim this chapter and quickly move to Chapter 2. However, we find that a bit of review is never a waste of time.

Chapter 2 introduces the ideas behind algorithm analysis, with an emphasis on Big-O notation. In addition we do an analysis of the key Python data structures used throughout the book. This helps students understand the tradeoffs between different implementations of the various abstract data types. This chapter also includes examples of experimental measurement of Java primitives used at runtime.

Chapters 3 through 7 provide a thorough mix of algorithms and data structures, often presented in context of a classic computer science problem. Although there is some latitude in terms of order, many of the topics have a sequential dependency and should be completed in the order provided. For example, in Chapter 3, we introduce stacks. We use stacks to explain recursion in Chapter 4 and then use recursion to implement binary search in Chapter 5.

Chapter 8, Additional Topics, is an optional chapter consisting of individual sections, each of which is linked back to a previous chapter. As of this writing, it has not been converted to Java, as it will not be covered in the first iteration of the course using this book in Spring 2024. As noted in the organization chart, it is possible to take these topics together after completing Chapter 7. The individual sections can also be linked to their specific chapters. For example, instructors wishing to introduce arrays early can move to Section 8.1 immediately after Chapter 3.