Data abstraction & 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.

• Preface p. xv
• Chapter Dependency Chart p. xviii
• Part 1 Problem-Solving Techniques p. 1
• 1 Review of Java Fundamentals p. 3
• 1.1 Language Basics p. 4
• Comments p. 4
• Identifiers and Keywords p. 4
• Variables p. 4
• Primitive Data Types p. 5
• References p. 6
• Literal Constants p. 6
• Named Constants p. 7
• Assignments and Expressions p. 8
• Arrays p. 11
• 1.2 Selection Statements p. 14
• The if Statement p. 15
• The switch Statement p. 16
• 1.3 Iteration Statements p. 17
• The while Statement p. 17
• The for Statement p. 18
• The do Statement p. 21
• 1.4 Program Structure p. 21
• Packages p. 22
• Classes p. 23
• Data Fields p. 24
• Methods p. 26
• How to Access Members of an Object p. 30
• Class Inheritance p. 30
• 1.5 Useful Java Classes p. 32
• The Object Class p. 32
• The Array Class p. 34
• String Classes p. 35
• 1.6 Java Exceptions p. 40
• Catching Exceptions p. 40
• Throwing Exceptions p. 47
• 1.7 Text Input and Output p. 49
• Input p. 49
• Output p. 51
• The Console Class p. 54
• 1.8 File Input and Output p. 56
• Text Files p. 58
• Object Serialization p. 66
• Summary p. 69
• Cautions p. 72
• Self-Test Exercises p. 72
• Exercises p. 73
• Programming Problems p. 78
• 2 Principles of Programming and Software Engineering p. 81
• 2.1 Problem Solving and Software Engineering p. 82
• What Is Problem Solving? p. 82
• The Life Cycle of Software p. 83
• What Is a Good Solution? p. 93
• 2.2 Achieving an Object-Oriented Design p. 95
• Abstraction and Information Hiding p. 96
• Object-Oriented Design p. 98
• Functional Decomposition p. 100
• General Design Guidelines p. 101
• Modeling Object-Oriented Designs Using UML p. 102
• Advantages of an Object-Oriented Approach p. 106
• 2.3 A Summary of Key Issues in Programming p. 107
• Modularity p. 107
• Modifiability p. 109
• Ease of Use p. 111
• Fail-Safe Programming p. 112
• Style p. 118
• Debugging p. 122
• Summary p. 125
• Cautions p. 126
• Self-Test Exercises p. 126
• Exercises p. 127
• Programming Problems p. 132
• 3 Recursion: The Mirrors p. 137
• 3.1 Recursive Solutions p. 138
• A Recursive Valued Method: The Factorial of n p. 141
• A Recursive void Method: Writing a String Backward p. 148
• 3.2 Counting Things p. 159
• Multiplying Rabbits (The Fibonacci Sequence) p. 159
• Organizing a Parade p. 161
• Mr. Spock's Dilemma (Choosing k out of n Things) p. 164
• 3.3 Searching an Array p. 166
• Finding the Largest Item in an Array p. 167
• Binary Search p. 168
• Finding the k th Smallest Item in an Array p. 172
• 3.4 Organizing Data p. 176
• The Towers of Hanoi p. 176
• 3.5 Recursion and Efficiency p. 180
• Summary p. 187
• Cautions p. 187
• Self-Test Exercises p. 188
• Exercises p. 189
• Programming Problems p. 195
• 4 Data Abstraction: The Walls p. 197
• 4.1 Abstract Data Types p. 198
• 4.2 Specifying ADTs p. 203
• The ADT List p. 204
• The ADT Sorted List p. 209
• Designing an ADT p. 211
• Axioms (Optional) p. 215
• 4.3 Implementing ADTs p. 218
• Java Classes Revisited p. 219
• Java Interfaces p. 221
• Java Packages p. 224
• An Array-Based Implementation of the ADT List p. 226
• Summary p. 233
• Cautions p. 233
• Self-Test Exercises p. 234
• Exercises p. 235
• Programming Problems p. 238
• 5 Linked Lists p. 241
• 5.1 Preliminaries p. 242
• Object References p. 242
• Resizeable Arrays p. 248
• Reference-Based Linked Lists p. 249
• 5.2 Programming with Linked Lists p. 253
• Displaying the Contents of a Linked List p. 253
• Deleting a Specified Node from a Linked List p. 255
• Inserting a Node into a Specified Position of a Linked List p. 258
• A Reference-Based Implementation of the ADT List p. 264
• Comparing Array-Based and Reference-Based Implementations p. 268
• Passing a Linked List to a Method p. 271
• Processing Linked Lists Recursively p. 271
• 5.3 Variations of the Linked List p. 277
• Tail References p. 277
• Circular Linked Lists p. 278
• Dummy Head Nodes p. 280
• Doubly Linked Lists p. 280
• 5.4 Application: Maintaining an Inventory p. 284
• 5.5 The Java Collections Framework p. 290
• Generics p. 291
• Iterators p. 292
• The Java Collection's Framework List Interface p. 295
• Summary p. 298
• Cautions p. 300
• Self-Test Exercises p. 301
• Exercises p. 303
• Programming Problems p. 307
• Part 2 Problem Solving with Abstract Data Types p. 313
• 6 Recursion as a Problem-Solving Technique p. 315
• 6.1 Backtracking p. 316
• The Eight Queens Problem p. 316
• 6.2 Defining Languages p. 321
• The Basics of Grammars p. 322
• Two Simple Languages p. 323
• Algebraic Expressions p. 326
• 6.3 The Relationship Between Recursion and Mathematical Induction p. 336
• The Correctness of the Recursive Factorial Method p. 336
• The Cost of Towers of Hanoi p. 337
• Summary p. 339
• Cautions p. 339
• Self-Test Exercises p. 340
• Exercises p. 340
• Programming Problems p. 344
• 7 Stacks p. 351
• 7.1 The Abstract Data Type Stack p. 352
• Developing an ADT During the Design of a Solution p. 352
• 7.2 Simple Applications of the ADT Stack p. 358
• Checking for Balanced Braces p. 358
• Recognizing Strings in a Language p. 362
• 7.3 Implementations of the ADT Stack p. 363
• An Array-Based Implementation of the ADT Stack p. 365
• A Reference-Based Implementation of the ADT Stack p. 367
• An Implementation That Uses the ADT List p. 369
• Comparing Implementations p. 371
• The Java Collections Framework Class Stack p. 371
• 7.4 Application: Algebraic Expressions p. 373
• Evaluating Postfix Expressions p. 373
• Converting Infix Expressions to Equivalent Postfix Expressions p. 375
• 7.5 Application: A Search Problem p. 378
• A Nonrecursive Solution That Uses a Stack p. 380
• A Recursive Solution p. 388
• 7.6 The Relationship Between Stacks and Recursion p. 391
• Summary p. 393
• Cautions p. 393
• Self-Test Exercises p. 394
• Exercises p. 395
• Programming Problems p. 400
• 8 Queues p. 409
• 8.1 The Abstract Data Type Queue p. 410
• 8.2 Simple Applications of the ADT Queue p. 412
• Reading a String of Characters p. 412
• Recognizing Palindromes p. 413
• 8.3 Implementations of the ADT Queue p. 414
• A Reference-Based Implementation p. 416
• An Array-Based Implementation p. 419
• An Implementation That Uses the ADT List p. 425
• The JCF Interfaces Queue and Deque p. 426
• Comparing Implementations p. 432
• 8.4 A Summary of Position-Oriented ADTs p. 433
• 8.5 Application: Simulation p. 434
• Summary p. 444
• Cautions p. 445
• Self-Test Exercises p. 445
• Exercises p. 446
• Programming Problems p. 450
• 9 Advanced Java Topics p. 455
• 9.1 Inheritance Revisited p. 456
• Java Access Modifiers p. 462
• Is-a and Has-a Relationships p. 464
• 9.2 Dynamic Binding and Abstract Classes p. 466
• Abstract Classes p. 469
• Java Interfaces Revisited p. 474
• 9.3 Java Generics p. 475
• Generic Classes p. 475
• Generic Wildcards p. 477
• Generic Classes and Inheritance p. 478
• Generic Implementation of the Class List p. 481
• Generic Methods p. 483
• 9.4 The ADTs List and Sorted List Revisited p. 484
• Implementations of the ADT Sorted List That Use the ADT List p. 485
• 9.5 Iterators p. 489
• Summary p. 493
• Cautions p. 494
• Self-Test Exercises p. 494
• Exercises p. 495
• Programming Problems p. 500
• 10 Algorithm Efficiency and Sorting p. 505
• 10.1 Measuring the Efficiency of Algorithms p. 506
• The Execution Time of Algorithms p. 507
• Algorithm Growth Rates p. 509
• Order-of-Magnitude Analysis and Big O Notation p. 509
• Keeping Your Perspective p. 515
• The Efficiency of Searching Algorithms p. 517
• 10.2 Sorting Algorithms and Their Efficiency p. 518
• Selection Sort p. 519
• Bubble Sort p. 523
• Insertion Sort p. 525
• Mergesort p. 527
• Quicksort p. 533
• Radix Sort p. 545
• A Comparison of Sorting Algorithms p. 547
• The Java Collections Framework Sort Algorithm p. 548
• Summary p. 552
• Cautions p. 553
• Self-Test Exercises p. 553
• Exercises p. 554
• Programming Problems p. 558
• 11 Trees p. 561
• 11.1 Terminology p. 562
• 11.2 The ADT Binary Tree p. 570
• Basic Operations of the ADT Binary Tree p. 570
• General Operations of the ADT Binary Tree p. 571
• Traversals of a Binary Tree p. 574
• Possible Representations of a Binary Tree p. 577
• A Reference-Based Implementation of the ADT Binary Tree p. 581
• Tree Traversals Using an Iterator p. 586
• 11.3 The ADT Binary Search Tree p. 594
• Algorithms for the Operations of the ADT Binary Search Tree p. 600
• A Reference-Based Implementation of the ADT Binary Search Tree p. 615
• The Efficiency of Binary Search Tree Operations p. 619
• Treesort p. 624
• Saving a Binary Search Tree in a File p. 625
• The JCF Binary Search Algorithm p. 628
• 11.4 General Trees p. 629
• Summary p. 631
• Cautions p. 632
• Self-Test Exercises p. 632
• Exercises p. 634
• Programming Problems p. 640
• 12 Tables and Priority Queues p. 643
• 12.1 The ADT Table p. 644
• Selecting an Implementation p. 651
• A Sorted Array-Based Implementation of the ADT Table p. 658
• A Binary Search Tree Implementation of the ADT Table p. 661
• 12.2 The ADT Priority Queue: A Variation of the ADT Table p. 663
• Heaps p. 667
• A Heap Implementation of the ADT Priority Queue p. 676
• Heapsort p. 678
• 12.3 Tables and Priority Queues in the JCF p. 681
• The JCF Map Interface p. 681
• The JCF Set Interface p. 685
• The JCF PriorityQueue Class p. 689
• Summary p. 691
• Cautions p. 692
• Self-Test Exercises p. 692
• Exercises p. 693
• Programming Problems p. 696
• 13 Advanced Implementations of Tables p. 699
• 13.1 Balanced Search Trees p. 700
• 2-3 Trees p. 701
• 2-3-4 Trees p. 721
• Red-Black Trees p. 728
• AVL Trees p. 731
• 13.2 Hashing p. 737
• Hash Functions p. 741
• Resolving Collisions p. 743
• The Efficiency of Hashing p. 752
• What Constitutes a Good Hash Function? p. 755
• Table Traversal: An Inefficient Operation under Hashing p. 757
• The JCF Hashtable and TreeMap Classes p. 758
• The Hashtable Class p. 758
• The TreeMap Class p. 761
• 13.3 Data with Multiple Organizations p. 764
• Summary p. 769
• Cautions p. 770
• Self-Test Exercises p. 771
• Exercises p. 771
• Programming Problems p. 774
• 14 Graphs p. 777
• 14.1 Terminology p. 778
• 14.2 Graphs as ADTs p. 781
• Implementing Graphs p. 782
• Implementing a Graph Class Using the JCF p. 785
• 14.3 Graph Traversals p. 788
• Depth-First Search p. 790
• Breadth-First Search p. 791
• Implementing a BFS Iterator Class Using the JCF p. 793
• 14.4 Applications of Graphs p. 796
• Topological Sorting p. 796
• Spanning Trees p. 799
• Minimum Spanning Trees p. 804
• Shortest Paths p. 807
• Circuits p. 811
• Some Difficult Problems p. 814
• Summary p. 815
• Cautions p. 816
• Self-Test Exercises p. 816
• Exercises p. 817
• Programming Problems p. 820
• 15 External Methods p. 823
• 15.1 A Look at External Storage p. 824
• 15.2 Sorting Data in an External File p. 827
• 15.3 External Tables p. 835
• Indexing an External File p. 837
• External Hashing p. 841
• B-Trees p. 845
• Traversals p. 855
• Multiple Indexing p. 857
• Summary p. 858
• Cautions p. 859
• Self-Test Exercises p. 859
• Exercises p. 859
• Programming Problems p. 862
• A A Comparison of Java to C++ p. 863
• B Unicode Character Codes (ASCII Subset) p. 867
• C Java Resources p. 868
• Java Web Sites p. 868
• Using Java SE 6 p. 868
• Integrated Development Environments (IDEs) p. 869
• D Mathematical Induction p. 870
• Example 1 p. 870
• Example 2 p. 871
• Example 3 p. 872
• Example 4 p. 873
• Example 5 p. 873
• Self-Test Exercises p. 874
• Exercises p. 874
• Glossary p. 877
• Self-Test Answers p. 897
• Index p. 921