Data Abstraction and Problem Solving with Java: Walls and Mirrors

The Third Edition of Data Abstraction and Problem Solving with Java: Walls and Mirrors employs the analogies of Walls (data abstraction) and Mirrors (recursion) to teach Java programming design solutions, in a way that beginning students find accessible. The book has a student-friendly pedagogical approach that carefully accounts for the strengths and weaknesses of the Java language. With this book, students will gain a solid foundation in data abstraction, object-oriented programming, and other problem-solving techniques.

Table of Contents:
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

About the Author :
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: