Additional Information
Book Details
Abstract
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
| Section Title | Page | Action | Price |
|---|---|---|---|
| Cover | Cover | ||
| Contents | 7 | ||
| Preface | 15 | ||
| Chapter Dependency Chart | 18 | ||
| PART ONE: Problem-Solving Techniques | 25 | ||
| 1 Review of Java Fundamentals | 27 | ||
| 1.1 Language Basics | 28 | ||
| Comments | 28 | ||
| Identifiers and Keywords | 28 | ||
| Variables | 28 | ||
| Primitive Data Types | 29 | ||
| References | 30 | ||
| Literal Constants | 30 | ||
| Named Constants | 31 | ||
| Assignments and Expressions | 32 | ||
| Arrays | 35 | ||
| 1.2 Selection Statements | 38 | ||
| The if Statement | 39 | ||
| The switch Statement | 40 | ||
| 1.3 Iteration Statements | 41 | ||
| The while Statement | 41 | ||
| The for Statement | 42 | ||
| The do Statement | 45 | ||
| 1.4 Program Structure | 45 | ||
| Packages | 46 | ||
| Classes | 47 | ||
| Data Fields | 48 | ||
| Methods | 50 | ||
| How to Access Members of an Object | 54 | ||
| Class Inheritance | 54 | ||
| 1.5 Useful Java Classes | 56 | ||
| The Object Class | 56 | ||
| The Array Class | 58 | ||
| String Classes | 59 | ||
| 1.6 Java Exceptions | 64 | ||
| Catching Exceptions | 64 | ||
| Throwing Exceptions | 71 | ||
| 1.7 Text Input and Output | 73 | ||
| Input | 73 | ||
| Output | 75 | ||
| The Console Class | 78 | ||
| 1.8 File Input and Output | 80 | ||
| Text Files | 82 | ||
| Object Serialization | 90 | ||
| Summary | 93 | ||
| Cautions | 96 | ||
| Self-Test Exercises | 96 | ||
| Exercises | 97 | ||
| Programming Problems | 102 | ||
| 2 Principles of Programming and Software Engineering | 105 | ||
| 2.1 Problem Solving and Software Engineering | 106 | ||
| What Is Problem Solving? | 106 | ||
| The Life Cycle of Software | 107 | ||
| What Is a Good Solution? | 117 | ||
| 2.2 Achieving an Object-Oriented Design | 119 | ||
| Abstraction and Information Hiding | 120 | ||
| Object-Oriented Design | 122 | ||
| Functional Decomposition | 124 | ||
| General Design Guidelines | 125 | ||
| Modeling Object-Oriented Designs Using UML | 126 | ||
| Advantages of an Object-Oriented Approach | 130 | ||
| 2.3 A Summary of Key Issues in Programming | 131 | ||
| Modularity | 131 | ||
| Modifiability | 133 | ||
| Ease of Use | 135 | ||
| Fail-Safe Programming | 136 | ||
| Style | 142 | ||
| Debugging | 146 | ||
| Summary | 149 | ||
| Cautions | 150 | ||
| Self-Test Exercises | 150 | ||
| Exercises | 151 | ||
| Programming Problems | 156 | ||
| 3 Recursion: The Mirrors | 161 | ||
| 3.1 Recursive Solutions | 162 | ||
| A Recursive Valued Method: The Factorial of n | 165 | ||
| A Recursive void Method: Writing a String Backward | 172 | ||
| 3.2 Counting Things | 183 | ||
| Multiplying Rabbits (The Fibonacci Sequence) | 183 | ||
| Organizing a Parade | 185 | ||
| Mr. Spock’s Dilemma (Choosing k out of n Things) | 188 | ||
| 3.3 Searching an Array | 190 | ||
| Finding the Largest Item in an Array | 191 | ||
| Binary Search | 192 | ||
| Finding the kth Smallest Item in an Array | 196 | ||
| 3.4 Organizing Data | 200 | ||
| The Towers of Hanoi | 200 | ||
| 3.5 Recursion and Efficiency | 204 | ||
| Summary | 211 | ||
| Cautions | 211 | ||
| Self-Test Exercises | 212 | ||
| Exercises | 213 | ||
| Programming Problems | 219 | ||
| 4 Data Abstraction: The Walls | 221 | ||
| 4.1 Abstract Data Types | 222 | ||
| 4.2 Specifying ADTs | 227 | ||
| The ADT List | 228 | ||
| The ADT Sorted List | 233 | ||
| Designing an ADT | 235 | ||
| Axioms (Optional) | 239 | ||
| 4.3 Implementing ADTs | 242 | ||
| Java Classes Revisited | 243 | ||
| Java Interfaces | 245 | ||
| Java Packages | 248 | ||
| An Array-Based Implementation of the ADT List | 250 | ||
| Summary | 257 | ||
| Cautions | 257 | ||
| Self-Test Exercises | 258 | ||
| Exercises | 259 | ||
| Programming Problems | 262 | ||
| 5 Linked Lists | 265 | ||
| 5.1 Preliminaries | 266 | ||
| Object References | 266 | ||
| Resizeable Arrays | 272 | ||
| Reference-Based Linked Lists | 273 | ||
| 5.2 Programming with Linked Lists | 277 | ||
| Displaying the Contents of a Linked List | 277 | ||
| Deleting a Specified Node from a Linked List | 279 | ||
| Inserting a Node into a Specified Position of a Linked List | 282 | ||
| A Reference-Based Implementation of the ADT List | 288 | ||
| Comparing Array-Based and Reference-Based Implementations | 292 | ||
| Passing a Linked List to a Method | 295 | ||
| Processing Linked Lists Recursively | 295 | ||
| 5.3 Variations of the Linked List | 301 | ||
| Tail References | 301 | ||
| Circular Linked Lists | 302 | ||
| Dummy Head Nodes | 304 | ||
| Doubly Linked Lists | 304 | ||
| 5.4 Application: Maintaining an Inventory | 308 | ||
| 5.5 The Java Collections Framework | 314 | ||
| Generics | 315 | ||
| Iterators | 316 | ||
| The Java Collection’s Framework List Interface | 319 | ||
| Summary | 322 | ||
| Cautions | 324 | ||
| Self-Test Exercises | 325 | ||
| Exercises | 327 | ||
| Programming Problems | 330 | ||
| PART TWO: Problem Solving with Abstract Data Types | 337 | ||
| 6 Recursion as a Problem-Solving Technique | 339 | ||
| 6.1 Backtracking | 340 | ||
| The Eight Queens Problem | 340 | ||
| 6.2 Defining Languages | 345 | ||
| The Basics of Grammars | 346 | ||
| Two Simple Languages | 347 | ||
| Algebraic Expressions | 350 | ||
| 6.3 The Relationship Between Recursion and Mathematical Induction | 360 | ||
| The Correctness of the Recursive Factorial Method | 360 | ||
| The Cost of Towers of Hanoi | 361 | ||
| Summary | 363 | ||
| Cautions | 363 | ||
| Self-Test Exercises | 364 | ||
| Exercises | 364 | ||
| Programming Problems | 368 | ||
| 7 Stacks | 375 | ||
| 7.1 The Abstract Data Type Stack | 376 | ||
| Developing an ADT During the Design of a Solution | 376 | ||
| 7.2 Simple Applications of the ADT Stack | 382 | ||
| Checking for Balanced Braces | 382 | ||
| Recognizing Strings in a Language | 386 | ||
| 7.3 Implementations of the ADT Stack | 387 | ||
| An Array-Based Implementation of the ADT Stack | 389 | ||
| A Reference-Based Implementation of the ADT Stack | 391 | ||
| An Implementation That Uses the ADT List | 393 | ||
| Comparing Implementations | 395 | ||
| The Java Collections Framework Class Stack | 395 | ||
| 7.4 Application: Algebraic Expressions | 397 | ||
| Evaluating Postfix Expressions | 397 | ||
| Converting Infix Expressions to Equivalent Postfix Expressions | 399 | ||
| 7.5 Application: A Search Problem | 402 | ||
| A Nonrecursive Solution That Uses a Stack | 404 | ||
| A Recursive Solution | 412 | ||
| 7.6 The Relationship Between Stacks and Recursion | 415 | ||
| Summary | 417 | ||
| Cautions | 417 | ||
| Self-Test Exercises | 418 | ||
| Exercises | 419 | ||
| Programming Problems | 424 | ||
| 8 Queues | 433 | ||
| 8.1 The Abstract Data Type Queue | 434 | ||
| 8.2 Simple Applications of the ADT Queue | 436 | ||
| Reading a String of Characters | 436 | ||
| Recognizing Palindromes | 437 | ||
| 8.3 Implementations of the ADT Queue | 438 | ||
| A Reference-Based Implementation | 440 | ||
| An Array-Based Implementation | 443 | ||
| An Implementation That Uses the ADT List | 449 | ||
| The JCF Interfaces Queue and Deque | 450 | ||
| Comparing Implementations | 456 | ||
| 8.4 A Summary of Position-Oriented ADTs | 457 | ||
| 8.5 Application: Simulation | 458 | ||
| Summary | 468 | ||
| Cautions | 469 | ||
| Self-Test Exercises | 469 | ||
| Exercises | 470 | ||
| Programming Problems | 474 | ||
| 9 Advanced Java Topics | 479 | ||
| 9.1 Inheritance Revisited | 480 | ||
| Java Access Modifiers | 486 | ||
| Is-a and Has-a Relationships | 488 | ||
| 9.2 Dynamic Binding and Abstract Classes | 490 | ||
| Abstract Classes | 493 | ||
| Java Interfaces Revisited | 498 | ||
| 9.3 Java Generics | 499 | ||
| Generic Classes | 499 | ||
| Generic Wildcards | 501 | ||
| Generic Classes and Inheritance | 502 | ||
| Generic Implementation of the Class List | 505 | ||
| Generic Methods | 507 | ||
| 9.4 The ADTs List and Sorted List Revisited | 508 | ||
| Implementations of the ADT Sorted List That Use the ADT List | 509 | ||
| 9.5 Iterators | 513 | ||
| Summary | 517 | ||
| Cautions | 518 | ||
| Self-Test Exercises | 518 | ||
| Exercises | 519 | ||
| Programming Problems | 524 | ||
| 10 Algorithm Efficiency and Sorting | 529 | ||
| 10.1 Measuring the Efficiency of Algorithms | 530 | ||
| The Execution Time of Algorithms | 531 | ||
| Algorithm Growth Rates | 533 | ||
| Order-of-Magnitude Analysis and Big O Notation | 533 | ||
| Keeping Your Perspective | 539 | ||
| The Efficiency of Searching Algorithms | 541 | ||
| 10.2 Sorting Algorithms and Their Efficiency | 542 | ||
| Selection Sort | 543 | ||
| Bubble Sort | 547 | ||
| Insertion Sort | 549 | ||
| Mergesort | 551 | ||
| Quicksort | 557 | ||
| Radix Sort | 569 | ||
| A Comparison of Sorting Algorithms | 571 | ||
| The Java Collections Framework Sort Algorithm | 572 | ||
| Summary | 576 | ||
| Cautions | 577 | ||
| Self-Test Exercises | 577 | ||
| Exercises | 578 | ||
| Programming Problems | 582 | ||
| 11 Trees | 585 | ||
| 11.1 Terminology | 586 | ||
| 11.2 The ADT Binary Tree | 594 | ||
| Basic Operations of the ADT Binary Tree | 594 | ||
| General Operations of the ADT Binary Tree | 595 | ||
| Traversals of a Binary Tree | 598 | ||
| Possible Representations of a Binary Tree | 601 | ||
| A Reference-Based Implementation of the ADT Binary Tree | 605 | ||
| Tree Traversals Using an Iterator | 610 | ||
| 11.3 The ADT Binary Search Tree | 618 | ||
| Algorithms for the Operations of the ADT Binary Search Tree | 624 | ||
| A Reference-Based Implementation of the ADT Binary Search Tree | 639 | ||
| The Efficiency of Binary Search Tree Operations | 643 | ||
| Treesort | 648 | ||
| Saving a Binary Search Tree in a File | 649 | ||
| The JCF Binary Search Algorithm | 652 | ||
| 11.4 General Trees | 653 | ||
| Summary | 655 | ||
| Cautions | 656 | ||
| Self-Test Exercises | 656 | ||
| Exercises | 658 | ||
| Programming Problems | 664 | ||
| 12 Tables and Priority Queues | 667 | ||
| 12.1 The ADT Table | 668 | ||
| Selecting an Implementation | 675 | ||
| A Sorted Array-Based Implementation of the ADT Table | 682 | ||
| A Binary Search Tree Implementation of the ADT Table | 685 | ||
| 12.2 The ADT Priority Queue: A Variation of the ADT Table | 687 | ||
| Heaps | 691 | ||
| A Heap Implementation of the ADT Priority Queue | 700 | ||
| Heapsort | 702 | ||
| 12.3 Tables and Priority Queues in the JCF | 705 | ||
| The JCF Map Interface | 705 | ||
| The JCF Set Interface | 709 | ||
| The JCF PriorityQueue Class | 713 | ||
| Summary | 715 | ||
| Cautions | 716 | ||
| Self-Test Exercises | 716 | ||
| Exercises | 717 | ||
| Programming Problems | 720 | ||
| 13 Advanced Implementations of Tables | 723 | ||
| 13.1 Balanced Search Trees | 724 | ||
| 2-3 Trees | 725 | ||
| 2-3-4 Trees | 745 | ||
| Red-Black Trees | 752 | ||
| AVL Trees | 755 | ||
| 13.2 Hashing | 761 | ||
| Hash Functions | 765 | ||
| Resolving Collisions | 767 | ||
| The Efficiency of Hashing | 776 | ||
| What Constitutes a Good Hash Function? | 779 | ||
| Table Traversal: An Inefficient Operation under Hashing | 781 | ||
| The JCF Hashtable and TreeMap Classes | 782 | ||
| The Hashtable Class | 782 | ||
| The TreeMap Class | 785 | ||
| 13.3 Data with Multiple Organizations | 788 | ||
| Summary | 793 | ||
| Cautions | 794 | ||
| Self-Test Exercises | 795 | ||
| Exercises | 795 | ||
| Programming Problems | 798 | ||
| 14 Graphs | 801 | ||
| 14.1 Terminology | 802 | ||
| 14.2 Graphs as ADTs | 805 | ||
| Implementing Graphs | 806 | ||
| Implementing a Graph Class Using the JCF | 809 | ||
| 14.3 Graph Traversals | 812 | ||
| Depth-First Search | 814 | ||
| Breadth-First Search | 815 | ||
| Implementing a BFS Iterator Class Using the JCF | 817 | ||
| 14.4 Applications of Graphs | 820 | ||
| Topological Sorting | 820 | ||
| Spanning Trees | 823 | ||
| Minimum Spanning Trees | 828 | ||
| Shortest Paths | 831 | ||
| Circuits | 835 | ||
| Some Difficult Problems | 838 | ||
| Summary | 839 | ||
| Cautions | 840 | ||
| Self-Test Exercises | 840 | ||
| Exercises | 841 | ||
| Programming Problems | 844 | ||
| 15 External Methods | 847 | ||
| 15.1 A Look at External Storage | 848 | ||
| 15.2 Sorting Data in an External File | 851 | ||
| 15.3 External Tables | 859 | ||
| Indexing an External File | 861 | ||
| External Hashing | 865 | ||
| B-Trees | 869 | ||
| Traversals | 879 | ||
| Multiple Indexing | 881 | ||
| Summary | 882 | ||
| Cautions | 883 | ||
| Self-Test Exercises | 883 | ||
| Exercises | 883 | ||
| Programming Problems | 886 | ||
| A: A Comparison of Java to C | 887 | ||
| B: Unicode Character Codes (ASCII Subset) | 891 | ||
| C: Java Resources | 892 | ||
| Java Web Sites | 892 | ||
| Using Java SE 6 | 892 | ||
| Integrated Development Environments (IDEs) | 893 | ||
| D: Mathematical Induction | 894 | ||
| Example 1 | 894 | ||
| Example 2 | 895 | ||
| Example 3 | 896 | ||
| Example 4 | 897 | ||
| Example 5 | 897 | ||
| Self-Test Exercises | 898 | ||
| Exercises | 898 | ||
| Glossary | 901 | ||
| A | 901 | ||
| B | 902 | ||
| C | 904 | ||
| D | 905 | ||
| E | 906 | ||
| F | 907 | ||
| G | 908 | ||
| H | 908 | ||
| I | 909 | ||
| J | 910 | ||
| K | 911 | ||
| L | 911 | ||
| M | 912 | ||
| N | 912 | ||
| O | 912 | ||
| P | 913 | ||
| Q | 914 | ||
| R | 915 | ||
| S | 916 | ||
| T | 918 | ||
| U | 919 | ||
| V | 919 | ||
| W | 919 | ||
| Self-Test Answers | 921 | ||
| Index | 945 | ||
| Symbols | 945 | ||
| Numbers | 945 | ||
| A | 945 | ||
| B | 947 | ||
| C | 948 | ||
| D | 949 | ||
| E | 949 | ||
| F | 950 | ||
| G | 950 | ||
| H | 951 | ||
| I | 951 | ||
| J | 952 | ||
| K | 953 | ||
| L | 953 | ||
| M | 954 | ||
| N | 954 | ||
| O | 954 | ||
| P | 955 | ||
| Q | 955 | ||
| R | 956 | ||
| S | 956 | ||
| T | 958 | ||
| U | 959 | ||
| V | 959 | ||
| W | 959 | ||
| Z | 959 |