Data Structures and Problem Solving Using Java
(Second Edition)
Contents
Part I:  Tour of Java
CHAPTER 1: Primitive Java
1.1	The General Environment
1.2	The First Program
1.2.1	Comments
1.2.2	main
1.2.3	Terminal Output
1.3	Primitive Types
1.3.1	The Primitive Types
1.3.2	Constants
1.3.3	Declaration and Initialization of Primitive Types
1.3.4	Terminal Input and Output
1.4	Basic Operators
1.4.1	Assignment Operators
1.4.2	Binary Arithmetic Operators
1.4.3	Unary Operators
1.4.4	Type Conversions
1.5	Conditional Statements
1.5.1	Relational and Equality Operators
1.5.2	Logical Operators
1.5.3	The if Statement
1.5.4	The while Statement
1.5.5	The for Statement
1.5.6	The do Statement
1.5.7	break and continue
1.5.8	The switch Statement

1.5.9	The Conditional Operator
1.6	Methods
1.6.1	Overloading of Method Names
1.6.2	Storage Classes
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 2: Reference Types
2.1	What Is a Reference?
2.2	Basics of Objects and References
2.2.1	The Dot Operator (.)
2.2.2	Declaration of Objects
2.2.3	Garbage Collection
2.2.4	The Meaning of =
2.2.5	Parameter Passing
2.2.6	The Meaning of ==
2.2.7	No Operator Overloading for Objects
2.3	Strings
2.3.1	Basics of String Manipulation
2.3.2	String Concatenation
2.3.3	Comparing Strings
2.3.4	Other String Methods
2.3.5	Converting Other Types of Strings
2.4	Arrays
2.4.1	Declaration, Assignment, and Methods
2.4.2	Dynamic Array Expansion
2.4.3	ArrayList
2.4.4	Multidimensional Arrays

2.4.5	Command-line Arguments
2.5	Exception Handling
2.5.1	Processing Exceptions
2.5.2	The finally Clause
2.5.3	Common Exceptions
2.5.4	The throw and throws Clauses
2.6	Input and Output
2.6.1	Basic Stream Operations
2.6.2	The StringTokenizer Type
2.6.3	Sequential Files
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 3: Objects and Classes
3.1	What Is Object-oriented Programming?
3.2	A Simple Example
3.3	Javadoc
3.4	Basic Methods
3.4.1	Constructors
3.4.2	Mutators and Accessors
3.4.3	Output and toString
3.4.4	equals
3.4.5	main
3.4.6	static Fields and Methods
3.5	Additional Constructs
3.5.1	The this Reference
3.5.2	The this Shorthand for Constructors
3.5.3	The instanceof Operator

3.5.4	Instance Members vs. Static Members
3.5.5	Static Fields and Methods
3.5.6	Static Initializers
3.6	Packages
3.6.1	The import Directive
3.6.2	The package Statement
3.6.3	The CLASSPATH Environment Variable
3.6.4	Package Visibility Rules
3.7	A Design Pattern: Composite (Pair)
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 4: Inheritance
4.1	What Is Inheritance?
4.1.1	Creating New Classes
4.1.2	Type Compatability
4.1.3	Dynamic Binding and Polymorphism
4.1.4	Inheritance Hierarchies
4.1.5	Visibility Rules
4.1.6	The Constructor and super
4.1.7	final Methods and Classes
4.1.8	Overriding a Method
4.1.9	Type Compatability Revisited
4.2	Designing Hierarchies
4.2.1	Abstract Methods and Classes
4.3	Multiple Inheritance
4.4	The Interface
4.4.1	Specifying an Interface

4.4.2	Implementing an Interface
4.4.3	Multiple Interfaces
4.4.4	Interfaces are Abstract Classes
4.5	Fundamental Inheritance in Java
4.5.1	The Object Class
4.5.2	The Hierarchy of Exceptions
4.5.3	I/O: The Decorator Pattern
4.6	Implementing Generic Components
4.6.1	Using Object for Genericity
4.6.2	Wrappers for Primitive Types
4.6.3	Adapters: Changing an Interface
4.6.4	Using Interface Types for Genericity
4.7	The Functor (Function Objects)
4.7.1	Nested Classes
4.7.2	Local Classes
4.7.3	Anonymous Classes
4.8	Dynamic Binding Details
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
Part II:  Algorithms and Building Blocks
CHAPTER 5: Algorithm Analysis
5.1	What Is Algorithm Analysis?
5.2	Examples of Algorithm Running Times
5.3	The Maximum Contiguous Subsequence Sum Problem
5.3.1	The Obvious O(N 3) Algorithm

5.3.2	An Improved O(N 2) Algorithm
5.3.3	A Linear Algorithm
5.4	General Big-Oh Rules
5.5	The Logarithm
5.6	Static Searching Problem
5.6.1	Sequential Search
5.6.2	Binary Search
5.6.3	Interpolation Search
5.7	Checking an Algorithm Analysis
5.8	Limitations of Big-Oh Analysis
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 6: The Collections API
6.1	Introduction
6.2	The Iterator Pattern
6.2.1	Basic Iterator Design
6.2.2	Inheritance-based Iterators and Factories
6.3	Collections API: Containers and Iterators
6.3.1	The Collection interface
6.3.2	Iterator interface
6.4	Generic Algorithms
6.4.1	Comparator Function Objects
6.4.2	The Collections Class
6.4.3	Binary Search
6.4.4	Sorting
6.5	The List Interface
6.5.1	The ListIterator Interface

6.5.2	LinkedList class
6.6	Stacks and Queues
6.6.1	Stacks
6.6.2	Stacks and Computer Languages
6.6.3	Queues
6.6.4	Stacks and Queues in the Collections API
6.7	Sets
6.7.1	The TreeSet Class
6.7.2	The HashSet Container
6.8	Maps
6.9	Priority Queues
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 7: Recursion
7.1	What Is Recursion?
7.2	Background: Proofs by Mathematical Induction
7.3	Basic Recursion
7.3.1	Printing Numbers in Any Base
7.3.2	Why It Works
7.3.3	How It Works
7.3.4	Too Much Recursion Can Be Dangerous
7.3.5	Preview of Trees
7.3.6	Additional Examples
7.4	Numerical Applications
7.4.1	Modular Arithmetic
7.4.2	Modular Exponentiation
7.4.3	Greatest Common Divisor and Multiplicative Inverses

7.4.4	The RSA Cryptosystem
7.5	Divide-and-Conquer Algorithms
7.5.1	The Maximum Contiguous Subsequence Sum Problem
7.5.2	Analysis of a Basic Divide-and-Conquer Recurrence
7.5.3	A General Upper Bound for Divide-and-Conquer Running Times
7.6	Dynamic Programming
7.7	Backtracking Algorithms
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 8: Sorting Algorithms
8.1	Why Is Sorting Important?
8.2	Preliminaries
8.3	Analysis of the Insertion Sort and Other  Simple Sorts
8.4	Shellsort
8.4.1	Performance of Shellsort
8.5	Mergesort
8.5.1	Linear-time Merging of Sorted Arrays
8.5.2	The Mergesort Algorithm
8.6	Quicksort
8.6.1	The Quicksort Algorithm
8.6.2	Analysis of Quicksort
8.6.3	Picking the Pivot
8.6.4	A Partitioning Strategy
8.6.5	Keys Equal to the Pivot
8.6.6	Median-of-three Partitioning
8.6.7	Small Arrays
8.6.8	Java Quicksort Routine

8.7	Quickselect
8.8	A Lower Bound for Sorting
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 9: Randomization
9.1	Why Do We Need Random Numbers?
9.2	Random-number Generators
9.3	Nonuniform Random Numbers
9.4	Generating a Random Permutation
9.5	Randomized Algorithms
9.6	Randomized Primality Testing
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
Part III:  Applications
CHAPTER 10: Fun and Games
10.1	Word Search Puzzles
10.1.1	Theory
10.1.2	Java Implementation
10.2	The Game of Tic-Tac-Toe

10.2.1	Alpha-beta Pruning
10.2.2	Transposition Tables
10.2.3	Computer Chess
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 11: Stacks and Compilers
11.1	Balanced-Symbol Checker
11.1.1	Basic Algorithm
11.1.2	Implementation
11.2	A Simple Calculator
11.2.1	Postfix Machines
11.2.2	Infix to Postfix Conversion
11.2.3	Implementation
11.2.4	Expression Trees
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 12: Utilities
12.1	 File Compression
12.1.1	Prefix Codes
12.1.2	Huffman’s Algorithm
12.1.3	Implementation
12.2	A Cross-reference Generator

12.2.1	Basic Ideas
12.2.2	Java Implementation
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 13: Simulation
13.1	The Josephus Problem
13.1.1	The Simple Solution
13.1.2	A More Efficient Algorithm
13.2	Event-driven Simulation
13.2.1	Basic Ideas
13.2.2	Example: A Modem Bank Simulation
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
CHAPTER 14: Graphs and Paths
14.1	Definitions
14.1.1	Representation
14.2	Unweighted Shortest-path Problem
14.2.1	Theory
14.2.2	Java Implementation
14.3	Positive-weighted, Shortest-path Problem
14.3.1	Theory: Dijkstra’s Algorithm
14.3.2	Java Implementation
14.4	Negative-weighted, Shortest-path Problem

14.4.1	Theory
14.4.2	Java Implementation
14.5	Path Problems in Acyclic Graphs
14.5.1	Topological Sorting
14.5.2	Theory of the Acyclic Shortest-path Algorithm
14.5.3	Java Implementation
14.5.4	An Application: Critical-path Analysis
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
Part IV:  Implementations
CHAPTER 15: Inner Classes and ArrayList Implementation
15.1	Iterators and Nested Classes
15.2	Iterators and Inner Classes
15.3	The AbstractCollection Class
15.4	Implementation of ArrayList with an Iterator
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
CHAPTER 16: Stacks and Queues
16.1	Dynamic Array Implementations
16.1.1	Stacks

16.1.2	Queues
16.2	Linked-list Implementations
16.2.1	Stacks
16.2.2	Queues
16.3	Comparison of the Two Methods
16.4	The java.util.Stack Class
16.5	Double-Ended Queues
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
CHAPTER 17: Linked Lists
17.1	Basic Ideas
17.1.1	Header Nodes
17.1.2	Iterator Classes
17.2	Java  Implementation
17.3	Doubly Linked Lists and Circular Linked Lists
17.4	Sorted Linked Lists
17.5	Implementing the Collections API LinkedList Class
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
CHAPTER 18: Trees
18.1	General Trees
18.1.1	Definitions
18.1.2	Implementation
18.1.3	An Application: File Systems

18.2	Binary Trees
18.3	Recursion and Trees
18.4	Tree Traversal: Iterator Classes
18.4.1	Postorder Traversal
18.4.2	Inorder Traversal
18.4.3	Preorder Traversal
18.4.4	Level-order Traversals
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
CHAPTER 19: Binary Search Trees
19.1	Basic Ideas
19.1.1	The Operations
19.1.2	Java Implementation
19.2	Order Statistics
19.2.1	Java Implementation
19.3	Analysis of Binary Search Tree Operations
19.4	AVL Trees
19.4.1	Properties
19.4.2	Single Rotation
19.4.3	Double Rotation
19.4.4	Summary of AVL Insertion
19.5	Red-Black Trees
19.5.1	Bottom-up Insertion
19.5.2	Top-down Red-Black Trees
19.5.3	Java Implementation
19.5.4	Top-down Deletion
19.6	AA-Trees
19.6.1	Insertion

19.6.2	Deletion
19.6.3	Java Implementation
19.7	Implementing the Collections API TreeSet and TreeMap Classes
19.8	B-Trees
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 20: Hash Tables
20.1	Basic Ideas
20.2	Hash Function
20.3	Linear Probing
20.3.1	Naive Analysis of Linear Probing
20.3.2	What Really Happens: Primary Clustering
20.3.3	Analysis of the find Operation
20.4	Quadratic Probing
20.4.1	Java Implementation
20.4.2	Analysis of Quadratic Probing
20.5	Separate Chaining Hashing
20.6	Hash Tables Versus Binary Search Trees
20.7	Hashing Applications
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 21: 
A Priority Queue: The Binary Heap
21.1	Basic Ideas
21.1.1	Structure Property
21.1.2	Heap-order Property
21.1.3	Allowed Operations
21.2	Implementation of the Basic Operations
21.2.1	The insert Operation
21.2.2	The deleteMin Operation
21.3	The buildHeap Operation: Linear-Time Heap Construction
21.4	Advanced Operations: decreaseKey and merge
21.5	Internal Sorting: Heapsort
21.6	External Sorting
21.6.1	Why We Need New Algorithms
21.6.2	Model for External Sorting
21.6.3	The Simple Algorithm
21.6.4	Multiway Merge
21.6.5	Polyphase Merge
21.6.6	Replacement Selection
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
Part V:  Advanced Data Structures
CHAPTER 22: Splay Trees
22.1	Self-Adjustment and Amortized Analysis
22.1.1	Amortized Time Bounds
22.1.2	A Simple Self-Adjusting Strategy (That Does Not Work)

22.2	The Basic Bottom-Up Splay Tree
22.3	Basic Splay Tree Operations
22.4	Analysis of Bottom-Up Splaying
22.4.1	Proof of the Splaying Bound
22.5	Top-Down Splay Trees
22.6	Implementation of Top-Down Splay Trees
22.7	Comparison of the Splay Tree with Other Search Trees
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 23: Merging Priority Queues
23.1	The Skew Heap
23.1.1	Merging Is Fundamental
23.1.2	Simplistic Merging of Heap-Ordered Trees
23.1.3	The Skew Heap: A Simple Modification
23.1.4	Analysis of the Skew Heap
23.2	The Pairing Heap
23.2.1	Pairing Heap Operations
23.2.2	Implementation of the Pairing Heap
23.2.3	Application: Dijkstra’s Shortest Weighted Path Algorithm
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
CHAPTER 24: 
The Disjoint Set Class
24.1	Equivalence Relations
24.2	Dynamic Equivalence and Two Applications
24.2.1	Application: Generating Mazes
24.2.2	Application: Minimum Spanning Trees
24.2.3	Application: The Nearest Common Ancestor Problem
24.3	The Quick-Find Algorithm
24.4	The Quick-Union Algorithm
24.4.1	Smart Union Algorithms
24.4.2	Path Compression
24.5	Java Implementation
24.6	Worst Case for Union-by-Rank and Path Compression
24.6.1	Analysis of the Union/Find Algorithm
Summary
Objects of the Game
Common Error
On the Internet
Exercises
References
APPENDICES
Index