The Third edition ofData Abstraction and Problem Solving with Java: Walls and Mirrorsemploys the analogies of Walls (data abstraction) and Mirrors (recursion) to teach Java programming design solutions, in a way that beginners find accessible. Readers will gain a solid foundation in data abstraction, object-oriented programming, and other problem-solving techniques. The first part of the book covers problem-solving techniques including a review of Java fundamentals, principles of programming and software engineering, recursion and data abstraction, and linked lists. Later chapters focus on problem solving with abstract data types including stacks, queues, algorithm efficiency and sorting, trees, and graphs. Readers searching for problem solving solutions through abstraction, algorithmic refinement, data structures and recursion.

**Dr. Janet Prichard** is an assistant professor at Bryant College where she teaches web design and development, object-oriented computing, operating systems, and data structures courses. She has a B.A. in mathematics from Providence College, and earned her M.S. and Ph.D. in computer science from the University of Rhode Island. Her academic interests include real-time databases, database query languages, object-oriented analysis and design methodologies, database standards, client-server models, and Internet security. Dr. Prichard is the lead author of the Third Edition of *Data Abstraction and Problem Solving with Java*.

**Frank M. Carrano** is Professor Emeritus of Computer Science at the University of Rhode Island. He received his Ph.D. degree in Computer Science from Syracuse University in 1969. His interests include data structures, computer science education, social issues in computing, and numerical computation. Professor Carrano is particularly interested in the design and delivery of undergraduate courses in computer science. He has authored several well-known computer science textbooks for undergraduates.

Frank’s Making it Real blog http://frank-m-carrano.com/blog/ extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science.

Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano

Find him on Facebook: https://www.facebook.com/makingitreal

Preface xv

Chapter Dependency Chart xviii

**PART ONE Problem-Solving Techniques 1**

**1 Review of Java Fundamentals 3**

1.1 Language Basics 4

Comments 4

Identifiers and Keywords 4

Variables 4

Primitive Data Types 5

References 6

Literal Constants 6

Named Constants 7

Assignments and Expressions 8

Arrays 11

1.2 Selection Statements 14

The if Statement 15

The switch Statement 16

1.3 Iteration Statements 17

The while Statement 17

The for Statement 18

The do Statement 21

1.4 Program Structure 21

Packages 22

Classes 23

Data Fields 24

Methods 26

How to Access Members of an Object 30

Class Inheritance 30

1.5 Useful Java Classes 32

The Object Class 32

The Array Class 34

String Classes 35

1.6 Java Exceptions 40

Catching Exceptions 40

Throwing Exceptions 47

1.7 Text Input and Output 49

Input 49

Output 51

The Console Class 54

1.8 File Input and Output 56

Text Files 58

Object Serialization 66

Summary 69 Cautions 72 Self-Test Exercises 72

Exercises 73 Programming Problems 78

**2 Principles of Programming and Software Engineering 81**

2.1 Problem Solving and Software Engineering 82

What Is Problem Solving? 82

The Life Cycle of Software 83

What Is a Good Solution? 93

2.2 Achieving an Object-Oriented Design 95

Abstraction and Information Hiding 96

Object-Oriented Design 98

Functional Decomposition 100

General Design Guidelines 101

Modeling Object-Oriented Designs Using UML 102

Advantages of an Object-Oriented Approach 106

2.3 A Summary of Key Issues in Programming 107

Modularity 107

Modifiability 109

Ease of Use 111

Fail-Safe Programming 112

Style 118

Debugging 122

Summary 125 Cautions 126 Self-Test Exercises 126

Exercises 127 Programming Problems 132

**3 Recursion: The Mirrors 137**

3.1 Recursive Solutions 138

A Recursive Valued Method: The Factorial of n 141

A Recursive void Method: Writing a String Backward 148

3.2 Counting Things 159

Multiplying Rabbits (The Fibonacci Sequence) 159

Organizing a Parade 161

Mr. Spock’s Dilemma (Choosing k out of n Things) 164

3.3 Searching an Array 166

Finding the Largest Item in an Array 167

Binary Search 168

Finding the k th Smallest Item in an Array 172

3.4 Organizing Data 176

The Towers of Hanoi 176

3.5 Recursion and Efficiency 180

Summary 187 Cautions 187 Self-Test Exercises 188

Exercises 189 Programming Problems 195

**4 Data Abstraction: The Walls 197**

4.1 Abstract Data Types 198

4.2 Specifying ADTs 203

The ADT List 204

The ADT Sorted List 209

Designing an ADT 211

Axioms (Optional) 215

4.3 Implementing ADTs 218

Java Classes Revisited 219

Java Interfaces 221

Java Packages 224

An Array-Based Implementation of the ADT List 226

Summary 233 Cautions 233 Self-Test Exercises 234

Exercises 235 Programming Problems 238

**5 Linked Lists 241**

5.1 Preliminaries 242

Object References 242

Resizeable Arrays 248

Reference-Based Linked Lists 249

5.2 Programming with Linked Lists 253

Displaying the Contents of a Linked List 253

Deleting a Specified Node from a Linked List 255

Inserting a Node into a Specified Position of a Linked List 258

A Reference-Based Implementation of the ADT List 264

Comparing Array-Based and Reference-Based Implementations 268

Passing a Linked List to a Method 271

Processing Linked Lists Recursively 271

5.3 Variations of the Linked List 277

Tail References 277

Circular Linked Lists 278

Dummy Head Nodes 280

Doubly Linked Lists 280

5.4 Application: Maintaining an Inventory 284

5.5 The Java Collections Framework 290

Generics 291

Iterators 292

The Java Collection’s Framework List Interface 295

Summary 298 Cautions 300 Self-Test Exercises 301

Exercises 303 Programming Problems 307

**PART TWOProblem Solving with Abstract Data Types 313**

6 Recursion as a Problem-Solving Technique 315

6.1 Backtracking 316

The Eight Queens Problem 316

6.2 Defining Languages 321

The Basics of Grammars 322

Two Simple Languages 323

Algebraic Expressions 326

6.3 The Relationship Between Recursion and Mathematical Induction 336

The Correctness of the Recursive Factorial Method 336

The Cost of Towers of Hanoi 337

Summary 339 Cautions 339 Self-Test Exercises 340

Exercises 340 Programming Problems 344

**7 Stacks 351**

7.1 The Abstract Data Type Stack 352

Developing an ADT During the Design of a Solution 352

7.2 Simple Applications of the ADT Stack 358

Checking for Balanced Braces 358

Recognizing Strings in a Language 362

7.3 Implementations of the ADT Stack 363

An Array-Based Implementation of the ADT Stack 365

A Reference-Based Implementation of the ADT Stack 367

An Implementation That Uses the ADT List 369

Comparing Implementations 371

The Java Collections Framework Class Stack 371

7.4 Application: Algebraic Expressions 373

Evaluating Postfix Expressions 373

Converting Infix Expressions to Equivalent Postfix Expressions 375

7.5 Application: A Search Problem 378

A Nonrecursive Solution That Uses a Stack 380

A Recursive Solution 388

7.6 The Relationship Between Stacks and Recursion 391

Summary 393 Cautions 393 Self-Test Exercises 394

Exercises 395 Programming Problems 400

**8 Queues 409**

8.1 The Abstract Data Type Queue 410

8.2 Simple Applications of the ADT Queue 412

Reading a String of Characters 412

Recognizing Palindromes 413

8.3 Implementations of the ADT Queue 414

A Reference-Based Implementation 416

An Array-Based Implementation 419

An Implementation That Uses the ADT List 425

The JCF Interfaces Queue and Deque 426

Comparing Implementations 432

8.4 A Summary of Position-Oriented ADTs 433

8.5 Application: Simulation 434

Summary 444 Cautions 445 Self-Test Exercises 445

Exercises 446 Programming Problems 450

**9 Advanced Java Topics 455**

9.1 Inheritance Revisited 456

Java Access Modifiers 462

Is-a and Has-a Relationships 464

9.2 Dynamic Binding and Abstract Classes 466

Abstract Classes 469

Java Interfaces Revisited 474

9.3 Java Generics 475

Generic Classes 475

Generic Wildcards 477

Generic Classes and Inheritance 478

Generic Implementation of the Class List 481

Generic Methods 483

9.4 The ADTs List and Sorted List Revisited 484

Implementations of the ADT Sorted List That Use the ADT List 485

9.5 Iterators 489

Summary 493 Cautions 494 Self-Test Exercises 494

Exercises 495 Programming Problems 500

**10 Algorithm Efficiency and Sorting 505**

10.1 Measuring the Efficiency of Algorithms 506

The Execution Time of Algorithms 507

Algorithm Growth Rates 509

Order-of-Magnitude Analysis and Big O Notation 509

Keeping Your Perspective 515

The Efficiency of Searching Algorithms 517

10.2 Sorting Algorithms and Their Efficiency 518

Selection Sort 519

Bubble Sort 523

Insertion Sort 525

Mergesort 527

Quicksort 533

Radix Sort 545

A Comparison of Sorting Algorithms 547

The Java Collections Framework Sort Algorithm 548

Summary 552 Cautions 553 Self-Test Exercises 553

Exercises 554 Programming Problems 558

**11 Trees 561**

11.1 Terminology 562

11.2 The ADT Binary Tree 570

Basic Operations of the ADT Binary Tree 570

General Operations of the ADT Binary Tree 571

Traversals of a Binary Tree 574

Possible Representations of a Binary Tree 577

A Reference-Based Implementation of the ADT Binary Tree 581

Tree Traversals Using an Iterator 586

11.3 The ADT Binary Search Tree 594

Algorithms for the Operations of the ADT Binary Search Tree 600

A Reference-Based Implementation

of the ADT Binary Search Tree 615

The Efficiency of Binary Search Tree Operations 619

Treesort 624

Saving a Binary Search Tree in a File 625

The JCF Binary Search Algorithm 628

11.4 General Trees 629

Summary 631 Cautions 632 Self-Test Exercises 632

Exercises 634 Programming Problems 640

**12 Tables and Priority Queues 643**

12.1 The ADT Table 644

Selecting an Implementation 651

A Sorted Array-Based Implementation of the ADT Table 658

A Binary Search Tree Implementation of the ADT Table 661

12.2 The ADT Priority Queue: A Variation of the ADT Table 663

Heaps 667

A Heap Implementation of the ADT Priority Queue 676

Heapsort 678

12.3 Tables and Priority Queues in the JCF 681

The JCF Map Interface 681

The JCF Set Interface 685

The JCF PriorityQueue Class 689

Summary 691 Cautions 692 Self-Test Exercises 692

Exercises 693 Programming Problems 696

**13 Advanced Implementations of Tables 699**

13.1 Balanced Search Trees 700

2-3 Trees 701

2-3-4 Trees 721

Red-Black Trees 728

AVL Trees 731

13.2 Hashing 737

Hash Functions 741

Resolving Collisions 743

The Efficiency of Hashing 752

What Constitutes a Good Hash Function? 755

Table Traversal: An Inefficient Operation under Hashing 757

The JCF Hashtable and TreeMap Classes 758

The Hashtable Class 758

The TreeMap Class 761

13.3 Data with Multiple Organizations 764

Summary 769 Cautions 770 Self-Test Exercises 771

Exercises 771 Programming Problems 774

**14 Graphs 777**

14.1 Terminology 778

14.2 Graphs as ADTs 781

Implementing Graphs 782

Implementing a Graph Class Using the JCF 785

14.3 Graph Traversals 788

Depth-First Search 790

Breadth-First Search 791

Implementing a BFS Iterator Class Using the JCF 793

14.4 Applications of Graphs 796

Topological Sorting 796

Spanning Trees 799

Minimum Spanning Trees 804

Shortest Paths 807

Circuits 811

Some Difficult Problems 814

Summary 815 Cautions 816 Self-Test Exercises 816

Exercises 817 Programming Problems 820

**15 External Methods 823**

15.1 A Look at External Storage 824

15.2 Sorting Data in an External File 827

15.3 External Tables 835

Indexing an External File 837

External Hashing 841

B-Trees 845

Traversals 855

Multiple Indexing 857

Summary 858 Cautions 859 Self-Test Exercises 859

Exercises 859 Programming Problems 862

A. A Comparison of Java to C++ 863

B. Unicode Character Codes (ASCII Subset) 867

C. Java Resources 868

Java Web Sites 868

Using Java SE 6 868

Integrated Development Environments (IDEs) 869

D. Mathematical Induction 870

Example 1 870

Example 2 871

Example 3 872

Example 4 873

Example 5 873

Self-Test Exercises 874 Exercises 874

Glossary 877

Self-Test Answers 897

Index 921