Algorithms in Java: Parts 1-4

Preface
Scope
Use in the Curriculum
Algorithms of Practical Use
Programming Language
Acknowledgments
Java Consultant's Preface
Notes on Exercises

Part I: Fundamentals

Introduction
Algorithms
A Sample Problem: Connectivity
Union-Find Algorithms
Perspective
Summary of Topics

Principles of Algorithm Analysis
Implementation and Empirical Analysis
Analysis of Algorithms
Growth of Functions
Big-Oh Notation
Basic Recurrences
Examples of Algorithm Analysis
Guarantees, Predictions, and Limitations

References for Part One

Part II: Data Structures

Elementary Data Structures
Building Blocks
Arrays
Linked Lists
Elementary List Processing
Memory Allocation for Lists
Strings
Compound Data Structures

Abstract Data Types
Exercises
Collections of Items
Pushdown Stack ADT
Examples of Stack ADT Clients
Stack ADT Implementations
Generic Implementations
Creation of a New ADT
FIFO Queues and Generalized Queues
Duplicate and Index Items
First-Class ADTs
app-Based ADT Example
Perspective

Recursion and Trees
Recursive Algorithms
Divide and Conquer
Dynamic Programming
Trees
Mathematical Properties of Binary Trees
Tree Traversal
Recursive Binary-Tree Algorithms
Graph Traversal
Perspective

References for Part Two

Part III: Sorting

Elementary Sorting Methods
Rules of the Game
Generic Sort Implementations
Selection Sort
Insertion Sort
Bubble Sort
Performance Characteristics of Elementary Sorts
Algorithm Visualization
Shellsort
Sorting of Linked Lists
Key-Indexed Counting

Quicksort
The Basic Algorithm
Performance Characteristics of Quicksort
Stack Size
Small Subfiles
Median-of-Three Partitioning
Duplicate Keys
Strings and Vectors
Selection

Merging and Mergesort
Two-Way Merging
Abstract In-Place Merge
Top-Down Mergesort
Improvements to the Basic Algorithm
Bottom-Up Mergesort
Performance Characteristics of Mergesort
Linked-List Implementations of Mergesort
Recursion Revisited

Priority Queues and Heapsort
Exercises
Elementary Implementations
Heap Data Structure
Algorithms on Heaps
Heapsort
Priority-Queue ADT
Priority Queues for Client Arrays
Binomial Queues

Radix Sorting
Bits, Bytes, and Words
Binary Quicksort
MSD Radix Sort
Three-Way Radix Quicksort
LSD Radix Sort
Performance Characteristics of Radix Sorts
Sublinear-Time Sorts

Special-Purpose Sorting Methods
Batcher's Odd-Even Mergesort
Sorting Networks
Sorting In Place
External Sorting
Sort-Merge Implementations
Parallel Sort-Merge

References for Part Three

Part IV: Searching

Symbol Tables and Binary Search Trees
Symbol-Table Abstract Data Type
Key-Indexed Search
Sequential Search
Binary Search
Index Implementations with Symbol Tables
Binary Search Trees
Performance Characteristics of BSTs
Insertion at the Root in BSTs
BST Implementations of Other ADT Operations

Balanced Trees
Exercises
Randomized BSTs
Splay BSTs
Top-Down 2-3-4 Trees
Red-Black Trees
Skip Lists
Performance Characteristics

Hashing
Hash Functions
Separate Chaining
Linear Probing
Double Hashing
Dynamic Hash Tables
Perspective

Radix Search
Digital Search Trees
Tries
Patricia Tries
Multiway Tries and TSTs
Text-String-Index Algorithms

External Searching
Rules of the Game
Indexed Sequential Access
B Trees
Extendible Hashing
Perspective

References for Part Four

Appendix
Exercises