| |

| |

Preface | |

| |

| |

Chapter Dependency Chart | |

| |

| |

| |

Problem-Solving Techniques | |

| |

| |

| |

Review of Java Fundamentals | |

| |

| |

| |

Language Basics | |

| |

| |

Comments | |

| |

| |

Identifiers and Keywords | |

| |

| |

Variables | |

| |

| |

Primitive Data Types | |

| |

| |

References | |

| |

| |

Literal Constants | |

| |

| |

Named Constants | |

| |

| |

Assignments and Expressions | |

| |

| |

Arrays | |

| |

| |

| |

Selection Statements | |

| |

| |

The if Statement | |

| |

| |

The switch Statement | |

| |

| |

| |

Iteration Statements | |

| |

| |

The while Statement | |

| |

| |

The for Statement | |

| |

| |

The do Statement | |

| |

| |

| |

Program Structure | |

| |

| |

Packages | |

| |

| |

Classes | |

| |

| |

Data Fields | |

| |

| |

Methods | |

| |

| |

How to Access Members of an Object | |

| |

| |

Class Inheritance | |

| |

| |

| |

Useful Java Classes | |

| |

| |

The Object Class | |

| |

| |

The Array Class | |

| |

| |

String Classes | |

| |

| |

| |

Java Exceptions | |

| |

| |

Catching Exceptions | |

| |

| |

Throwing Exceptions | |

| |

| |

| |

Text Input and Output | |

| |

| |

Input | |

| |

| |

Output | |

| |

| |

The Console Class | |

| |

| |

| |

File Input and Output | |

| |

| |

Text Files | |

| |

| |

Object Serialization | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Principles of Programming and Software Engineering | |

| |

| |

| |

Problem Solving and Software Engineering | |

| |

| |

What Is Problem Solving? | |

| |

| |

The Life Cycle of Software | |

| |

| |

What Is a Good Solution? | |

| |

| |

| |

Achieving an Object-Oriented Design | |

| |

| |

Abstraction and Information Hiding | |

| |

| |

Object-Oriented Design | |

| |

| |

Functional Decomposition | |

| |

| |

General Design Guidelines | |

| |

| |

Modeling Object-Oriented Designs Using UML | |

| |

| |

Advantages of an Object-Oriented Approach | |

| |

| |

| |

A Summary of Key Issues in Programming | |

| |

| |

Modularity | |

| |

| |

Modifiability | |

| |

| |

Ease of Use | |

| |

| |

Fail-Safe Programming | |

| |

| |

Style | |

| |

| |

Debugging | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Recursion: The Mirrors | |

| |

| |

| |

Recursive Solutions | |

| |

| |

A Recursive Valued Method: The Factorial of n | |

| |

| |

A Recursive void Method: Writing a String Backward | |

| |

| |

| |

Counting Things | |

| |

| |

Multiplying Rabbits (The Fibonacci Sequence) | |

| |

| |

Organizing a Parade | |

| |

| |

Mr. Spock's Dilemma (Choosing k out of n Things) | |

| |

| |

| |

Searching an Array | |

| |

| |

Finding the Largest Item in an Array | |

| |

| |

Binary Search | |

| |

| |

Finding the k th Smallest Item in an Array | |

| |

| |

| |

Organizing Data | |

| |

| |

The Towers of Hanoi | |

| |

| |

| |

Recursion and Efficiency | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Data Abstraction: The Walls | |

| |

| |

| |

Abstract Data Types | |

| |

| |

| |

Specifying ADTs | |

| |

| |

The ADT List | |

| |

| |

The ADT Sorted List | |

| |

| |

Designing an ADT | |

| |

| |

Axioms (Optional) | |

| |

| |

| |

Implementing ADTs | |

| |

| |

Java Classes Revisited | |

| |

| |

Java Interfaces | |

| |

| |

Java Packages | |

| |

| |

An Array-Based Implementation of the ADT List | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Linked Lists | |

| |

| |

| |

Preliminaries | |

| |

| |

Object References | |

| |

| |

Resizeable Arrays | |

| |

| |

Reference-Based Linked Lists | |

| |

| |

| |

Programming with Linked Lists | |

| |

| |

Displaying the Contents of a Linked List | |

| |

| |

Deleting a Specified Node from a Linked List | |

| |

| |

Inserting a Node into a Specified Position of a Linked List | |

| |

| |

A Reference-Based Implementation of the ADT List | |

| |

| |

Comparing Array-Based and Reference-Based Implementations | |

| |

| |

Passing a Linked List to a Method | |

| |

| |

Processing Linked Lists Recursively | |

| |

| |

| |

Variations of the Linked List | |

| |

| |

Tail References | |

| |

| |

Circular Linked Lists | |

| |

| |

Dummy Head Nodes | |

| |

| |

Doubly Linked Lists | |

| |

| |

| |

Application: Maintaining an Inventory | |

| |

| |

| |

The Java Collections Framework | |

| |

| |

Generics | |

| |

| |

Iterators | |

| |

| |

The Java Collection's Framework List Interface | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Problem Solving with Abstract Data Types | |

| |

| |

| |

Recursion as a Problem-Solving Technique | |

| |

| |

| |

Backtracking | |

| |

| |

The Eight Queens Problem | |

| |

| |

| |

Defining Languages | |

| |

| |

The Basics of Grammars | |

| |

| |

Two Simple Languages | |

| |

| |

Algebraic Expressions | |

| |

| |

| |

The Relationship Between Recursion and Mathematical Induction | |

| |

| |

The Correctness of the Recursive Factorial Method | |

| |

| |

The Cost of Towers of Hanoi | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Stacks | |

| |

| |

| |

The Abstract Data Type Stack | |

| |

| |

Developing an ADT During the Design of a Solution | |

| |

| |

| |

Simple Applications of the ADT Stack | |

| |

| |

Checking for Balanced Braces | |

| |

| |

Recognizing Strings in a Language | |

| |

| |

| |

Implementations of the ADT Stack | |

| |

| |

An Array-Based Implementation of the ADT Stack | |

| |

| |

A Reference-Based Implementation of the ADT Stack | |

| |

| |

An Implementation That Uses the ADT List | |

| |

| |

Comparing Implementations | |

| |

| |

The Java Collections Framework Class Stack | |

| |

| |

| |

Application: Algebraic Expressions | |

| |

| |

Evaluating Postfix Expressions | |

| |

| |

Converting Infix Expressions to Equivalent Postfix Expressions | |

| |

| |

| |

Application: A Search Problem | |

| |

| |

A Nonrecursive Solution That Uses a Stack | |

| |

| |

A Recursive Solution | |

| |

| |

| |

The Relationship Between Stacks and Recursion | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Queues | |

| |

| |

| |

The Abstract Data Type Queue | |

| |

| |

| |

Simple Applications of the ADT Queue | |

| |

| |

Reading a String of Characters | |

| |

| |

Recognizing Palindromes | |

| |

| |

| |

Implementations of the ADT Queue | |

| |

| |

A Reference-Based Implementation | |

| |

| |

An Array-Based Implementation | |

| |

| |

An Implementation That Uses the ADT List | |

| |

| |

The JCF Interfaces Queue and Deque | |

| |

| |

Comparing Implementations | |

| |

| |

| |

A Summary of Position-Oriented ADTs | |

| |

| |

| |

Application: Simulation | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Advanced Java Topics | |

| |

| |

| |

Inheritance Revisited | |

| |

| |

Java Access Modifiers | |

| |

| |

Is-a and Has-a Relationships | |

| |

| |

| |

Dynamic Binding and Abstract Classes | |

| |

| |

Abstract Classes | |

| |

| |

Java Interfaces Revisited | |

| |

| |

| |

Java Generics | |

| |

| |

Generic Classes | |

| |

| |

Generic Wildcards | |

| |

| |

Generic Classes and Inheritance | |

| |

| |

Generic Implementation of the Class List | |

| |

| |

Generic Methods | |

| |

| |

| |

The ADTs List and Sorted List Revisited | |

| |

| |

Implementations of the ADT Sorted List That Use the ADT List | |

| |

| |

| |

Iterators | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Algorithm Efficiency and Sorting | |

| |

| |

| |

Measuring the Efficiency of Algorithms | |

| |

| |

The Execution Time of Algorithms | |

| |

| |

Algorithm Growth Rates | |

| |

| |

Order-of-Magnitude Analysis and Big O Notation | |

| |

| |

Keeping Your Perspective | |

| |

| |

The Efficiency of Searching Algorithms | |

| |

| |

| |

Sorting Algorithms and Their Efficiency | |

| |

| |

Selection Sort | |

| |

| |

Bubble Sort | |

| |

| |

Insertion Sort | |

| |

| |

Mergesort | |

| |

| |

Quicksort | |

| |

| |

Radix Sort | |

| |

| |

A Comparison of Sorting Algorithms | |

| |

| |

The Java Collections Framework Sort Algorithm | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Trees | |

| |

| |

| |

Terminology | |

| |

| |

| |

The ADT Binary Tree | |

| |

| |

Basic Operations of the ADT Binary Tree | |

| |

| |

General Operations of the ADT Binary Tree | |

| |

| |

Traversals of a Binary Tree | |

| |

| |

Possible Representations of a Binary Tree | |

| |

| |

A Reference-Based Implementation of the ADT Binary Tree | |

| |

| |

Tree Traversals Using an Iterator | |

| |

| |

| |

The ADT Binary Search Tree | |

| |

| |

Algorithms for the Operations of the ADT Binary Search Tree | |

| |

| |

A Reference-Based Implementation of the ADT Binary Search Tree | |

| |

| |

The Efficiency of Binary Search Tree Operations | |

| |

| |

Treesort | |

| |

| |

Saving a Binary Search Tree in a File | |

| |

| |

The JCF Binary Search Algorithm | |

| |

| |

| |

General Trees | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Tables and Priority Queues | |

| |

| |

| |

The ADT Table | |

| |

| |

Selecting an Implementation | |

| |

| |

A Sorted Array-Based Implementation of the ADT Table | |

| |

| |

A Binary Search Tree Implementation of the ADT Table | |

| |

| |

| |

The ADT Priority Queue: A Variation of the ADT Table | |

| |

| |

Heaps | |

| |

| |

A Heap Implementation of the ADT Priority Queue | |

| |

| |

Heapsort | |

| |

| |

| |

Tables and Priority Queues in the JCF | |

| |

| |

The JCF Map Interface | |

| |

| |

The JCF Set Interface | |

| |

| |

The JCF PriorityQueue Class | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Advanced Implementations of Tables | |

| |

| |

| |

Balanced Search Trees | |

| |

| |

2-3 Trees | |

| |

| |

2-3-4 Trees | |

| |

| |

Red-Black Trees | |

| |

| |

AVL Trees | |

| |

| |

| |

Hashing | |

| |

| |

Hash Functions | |

| |

| |

Resolving Collisions | |

| |

| |

The Efficiency of Hashing | |

| |

| |

What Constitutes a Good Hash Function? | |

| |

| |

Table Traversal: An Inefficient Operation under Hashing | |

| |

| |

The JCF Hashtable and TreeMap Classes | |

| |

| |

The Hashtable Class | |

| |

| |

The TreeMap Class | |

| |

| |

| |

Data with Multiple Organizations | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

Graphs | |

| |

| |

| |

Terminology | |

| |

| |

| |

Graphs as ADTs | |

| |

| |

Implementing Graphs | |

| |

| |

Implementing a Graph Class Using the JCF | |

| |

| |

| |

Graph Traversals | |

| |

| |

Depth-First Search | |

| |

| |

Breadth-First Search | |

| |

| |

Implementing a BFS Iterator Class Using the JCF | |

| |

| |

| |

Applications of Graphs | |

| |

| |

Topological Sorting | |

| |

| |

Spanning Trees | |

| |

| |

Minimum Spanning Trees | |

| |

| |

Shortest Paths | |

| |

| |

Circuits | |

| |

| |

Some Difficult Problems | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

External Methods | |

| |

| |

| |

A Look at External Storage | |

| |

| |

| |

Sorting Data in an External File | |

| |

| |

| |

External Tables | |

| |

| |

Indexing an External File | |

| |

| |

External Hashing | |

| |

| |

B-Trees | |

| |

| |

Traversals | |

| |

| |

Multiple Indexing | |

| |

| |

Summary | |

| |

| |

Cautions | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Programming Problems | |

| |

| |

| |

A Comparison of Java to C++ | |

| |

| |

| |

Unicode Character Codes (ASCII Subset) | |

| |

| |

| |

Java Resources | |

| |

| |

Java Web Sites | |

| |

| |

Using Java SE 6 | |

| |

| |

Integrated Development Environments (IDEs) | |

| |

| |

| |

Mathematical Induction | |

| |

| |

Example 1 | |

| |

| |

Example 2 | |

| |

| |

Example 3 | |

| |

| |

Example 4 | |

| |

| |

Example 5 | |

| |

| |

Self-Test Exercises | |

| |

| |

Exercises | |

| |

| |

Glossary | |

| |

| |

Self-Test Answers | |

| |

| |

Index | |