The 5th edition of Data Structures and Abstractions with Java was given the 2019 Textbook Excellence Award from the Textbook and Academic Authors Association.  My co-author, Tim Henry, and I were honored to receive the award at the Association's 32nd annual conference in Philadelphia, Pennsylvania on June 24, 2019. The award recognizes "excellence in current textbooks and learning materials." Our book is published by Pearson Education.

Walls and Mirrors, 7th edition., receives the 2018 McGuffey Longevity Award

The 7th edition of Data Abstraction & Problem Solving: Walls and Mirrors was awarded the McGuffey Longevity Award from the Textbook and Academic Authors Association.  My co-author, Tim Henry, and I were honored to receive the award at the Association's 31st annual conference, which took place in Santa Fe, New Mexico. The award recognizes textbooks whose "excellence has been demonstrated over time." Indeed, the first edition of this book was published in 1995. Our 6th edition also received this award in 2016.

The 5th edition of Data Structures and Abstractions with Java is published

What’s New?

This new, 5th, edition of Data Structures and Abstractions with Java enhances the previous edition and continues its pedagogical approach to make the material accessible to students at the introductory level. The coverage that you enjoyed in previous editions is still here. As is usual for us, we have read every word of the previous edition and made changes to improve clarity and correctness. No chapter or interlude appears exactly as it did before. Our changes are motivated by reader suggestions and our own desire to improve the presentation.

In this new edition, we

• Adjusted the order of some topics.

• Added coverage of recursion in a new chapter that introduces grammars, languages, and  

  backtracking.

• Added additional Design Decisions, Notes, Security Notes, and Programming Tips 

  throughout the book.

• Added new exercises and programming projects, with an emphasis in areas of gaming, 

  e-commerce, and finance to most chapters.

• Refined our terminology, presentation, and word choices to ease understanding.

• Revised the illustrations to make them easier to read and to understand.

• Renamed Self-Test Questions as Study Questions and moved their answers to online. 

  We encourage our students to discuss their own answers with a study partner or group.

• Included the appendix about Java classes within the book instead of leaving it online.

• Reduced the amount of Java code given in the book.

• Ensured that all Java code is Java 9 compliant

And our table of contents:

 Introduction       Organizing Data

 Prelude               Designing Classes

 Chapter  1           Bags

 Java Interlude  1 Generics

 Chapter  2           Bag Implementations That Use Arrays

 Java Interlude  2 Exceptions

 Chapter  3           A Bag Implementation That Links Data

 Chapter  4           The Efficiency of Algorithms

 Chapter  5           Stacks

 Chapter  6           Stack Implementations

 Java Interlude  3 More About Exceptions 

 Chapter  7           Queues, Deques, and Priority Queues 

 Chapter  8           Queue, Deque, and Priority Queue Implementations 

 Chapter  9           Recursion 

 Chapter 10          Lists  

 Chapter 11          A List Implementation That Uses an Array

 Chapter 12          A List Implementation That Links Data  

 Java Interlude  4 Iterators 

 Chapter 13          Iterators for the ADT List 

 Chapter 14          Problem Solving With Recursion 

 Java Interlude  5 More About Generics 

 Chapter 15          An Introduction to Sorting 

 Chapter 16          Faster Sorting Methods 

 Java Interlude  6 Mutable and Immutable Objects 

 Chapter 17          Sorted Lists   

 Java Interlude  7 Inheritance and Polymorphism

 Chapter 18          Inheritance and Lists 

 Chapter 19         Searching 

 Java Interlude  8 Generics Once Again

 Chapter 20         Dictionaries 

 Chapter 21         Dictionary Implementations 

 Chapter 22         Introducing Hashing 

 Chapter 23         Hashing as a Dictionary Implementation 

 Chapter 24         Trees

 Chapter 25         Tree Implementations 

 Java Interlude  9 Cloning

 Chapter 26         A Binary Search Tree Implementation 

 Chapter 27         A Heap Implementation 

 Chapter 28         Balanced Search Trees 

 Chapter 29         Graphs 

 Chapter 30         Graph Implementations 

 Appendix A       Documentation and Programming Style

 Appendix B       Java Classes                                   

 Appendix C       Creating Classes from Other Classes 

Online Supplements:

 Supplement 1    Java Basics   

 Supplement 2    File Input and Output   

 Supplement 3    Glossary 

 Supplement 4    Answers to Study Questions

Study Tips

Here is a short You Tube video with some good ideas to help you learn! http://bit.ly/2l4etxj

A way to learn more when you study

"You can truly understand a topic when you have to teach it." Many teachers have heard and agreed with this statement. The Feynman Technique for studying is based on this advice. Check it out!

Tree traversals and C++11 lambda functions

One of our readers of Walls and Mirrors 7th edition had a problem with the traversal operation for TreeDictionary, which is described in section 18.2.2 of Chapter 18 (page 559). My co-author, Tim Henry, fielded the question, and I’m happy to share his response with you. The problem involves the data type of the traversal’s parameter, and the solution involves lambda functions, a feature of C++11 but one that we do not cover in the current edition of our book.

PROBLEM:

Recall that TreeDictionary stores its key-value entries in a binary search tree. The traversal operation is declared as follows:

/** Traverses the entries in this dictionary in sorted search-key order

    and calls a given client function once for the value in each entry. */

void TreeDictionaryValueType>::traverse(void visit(ValueType&)) const;

This function has a single parameter, which is a function whose only parameter is of type ValueType.

Our BinarySearchTree, as described in Chapter 16, stores entries of type ItemType, and declares the operation inorderTraverse as

void BinarySearchTree::inorderTraverse(void visit(ItemType&)) const;

TreeDictionary stores key-value pairs as objects of type Entry into the binary search tree entryTree. When you call TreeDictionary::traverse, the visit function you pass to it expects an argument of type ValueType. But when TreeDictionary::traverse calls BinarySearchTree::inorderTraverse using the statement

entryTree.inorderTraverse(visit);

visit expects an argument of type Entry. Therefore, the wrong type of argument is passed, and we get a compilation error.

GOAL: 

Find a way to “convert” visit into a function whose parameter is of type Entry  so we can pass it to inorderTraverse. Maybe a function something like this:

void someFunction(EntryValueType>& someEntry)

{

   auto someItem = someEntry.getItem(); // Must have an address for someItem

   visit(someItem);

}

But how do we give the function access to visit without changing its signature?

SOLUTION:

Lambda functions! Here is the new implementation for TreeDictionary::traverse:

TreeDictionary::traverse(void visit(ValueType&)) const

{

   auto treeVisit = [=](EntryValueType>& someEntry)

   {

      auto someItem = someEntry.getItem();

      visit(someItem);

   };

   entryTree.inorderTraverse(treeVisit);

}

The meaning of the previous lambda syntax follows:

[] means a lambda definition will follow. 

Only [] indicates to not “capture” or access local variables from the parent local environment. 

[&] means to access local variables as pass-by-reference. (This works for our scenario also.)

[=] means to access local variables as pass-by-copy (value). 

After the square brackets is the parameter list for the lambda function. In our case, it is the parameter type our tree needs: 

(EntryValueType>& someEntry)

Then we have the function implementation inside a pair of braces { } followed by a semicolon.

This works when the lambda function does not capture any local variables. 

BUT . . . 

We need to capture the local variable/parameter visit.

So we must use a more formal definition for the function parameters in the tree classes. (We could do this in TreeDictionary also, but it works without that change).

In BinaryTreeInterface.h, add:

#include

Then in the tree files

BinaryTreeInterface.h

BinaryNodeTree.h

BinaryNodeTree.cpp

BinarySearchTree.h

BinarySearchTree.cpp

change the signature of inorderTraverse so that it has the following parameter in red:

inorderTraverse(std::function visit)

This change relaxes some restrictions on how the lambda function can be passed as an argument. 

In BinaryNodeTree.h and BinaryNodeTree.cpp, you should also change the protected function inorder:

void inorder(std::function visit, 

                   std::shared_ptr> treePtr) const;

Make analogous changes to inorderTraverse and postorderTraverse.

Passwords: Should they die?

Source: Commit Strip via http://www.codeproject.com 

And check out the survey posted on networkworld.