Data Structures and Problem Solving Using Java (2/e) 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³) Algorithm
5.3.2 An Improved O(N²) 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