Home > Store

Data Abstraction and Problem Solving with Java: Walls and Mirrors, 3rd Edition

Register your product to gain access to bonus material or receive a coupon.

Data Abstraction and Problem Solving with Java: Walls and Mirrors, 3rd Edition

Book

  • Your Price: $181.32
  • List Price: $213.32
  • Usually ships in 24 hours.

About

Features

  • The Classic Walls & Mirrors approach instills the use of both abstraction (the walls) and recursion (the mirrors) to design solutions to problems
  • Completely revised code to be compatible with the Java 6 platform
  • Early (chapter 1) and expanded review of the Java language
  • Concentrates on the core data abstraction and data structure topics
  • Contains examples that illustrate the role of classes and ADTs in the problem-solving process
  • Includes carefully designed, student-friendly pedagogy, including margin notes, key concept boxes, error and misconception warnings, and self-test exercises with answers

SUPPLEMENTS

  • PowerPoint
  • Instructor’s Manual with Solutions
  • Test Bank
  • CourseSmart

Description

  • Copyright 2011
  • Dimensions: 7-3/8" x 9-1/8"
  • Pages: 960
  • Edition: 3rd
  • Book
  • ISBN-10: 0-13-212230-8
  • ISBN-13: 978-0-13-212230-6

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.

Sample Content

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

Updates

Submit Errata

More Information

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020