Algorithms in Java: Parts 1-4, Third Edition By Robert Sedgewick
Publisher:
Addison Wesley
Pub
Date: July 23, 2002
ISBN:
0-201-36120-5, 768 pages
Algorithms
in Java: Parts 1-4, Third Edition
Use in
the Curriculum
Algorithms
of Practical Use
Programming
Language
Acknowledgments
Java
Consultant's Preface
Notes
on Exercises
Part I:
Fundamentals
Chapter
1. Introduction
Section
1.1. Algorithms
Section
1.2. A Sample Problem: Connectivity
Section
1.3. Union–Find Algorithms
Section
1.4. Perspective
Section
1.5. Summary of Topics
Chapter
2. Principles of Algorithm Analysis
Section
2.1. Implementation and Empirical Analysis
Section
2.2. Analysis of Algorithms
Section
2.3. Growth of Functions
Section
2.4. Big-Oh Notation
Section
2.5. Basic Recurrences
Section
2.6. Examples of Algorithm Analysis
Section
2.7. Guarantees, Predictions, and Limitations
References
for Part One
Part
II: Data Structures
Chapter
3. Elementary Data Structures
Section
3.1. Building Blocks
Section
3.2. Arrays
Section
3.3. Linked Lists
Section
3.4. Elementary List Processing
Section
3.5. Memory Allocation for Lists
Section
3.6. Strings
Section
3.7. Compound Data Structures
Chapter
4. Abstract Data Types
Exercises
Section
4.1. Collections of Items
Section
4.2. Pushdown Stack ADT
Section
4.3. Examples of Stack ADT Clients
Section
4.4. Stack ADT Implementations
Section
4.5. Generic Implementations
Section
4.6. Creation of a New ADT
Section
4.7. FIFO Queues and Generalized Queues
Section
4.8. Duplicate and Index Items
Section
4.9. First-Class ADTs
Section
4.10. Application-Based ADT Example
Section
4.11. Perspective
Chapter
5. Recursion and Trees
Section
5.1. Recursive Algorithms
Section
5.2. Divide and Conquer
Section
5.3. Dynamic Programming
Section
5.4. Trees
Section
5.5. Mathematical Properties of Binary Trees
Section
5.6. Tree Traversal
Section
5.7. Recursive Binary-Tree Algorithms
Section
5.8. Graph Traversal
Section
5.9. Perspective
References
for Part Two
Part
III: Sorting
Chapter
6. Elementary Sorting Methods
Section
6.1. Rules of the Game
Section
6.2. Generic Sort Implementations
Section
6.3. Selection Sort
Section
6.4. Insertion Sort
Section
6.5. Bubble Sort
Section
6.6. Performance Characteristics of Elementary Sorts
Section
6.7. Algorithm Visualization
Section
6.8. Shellsort
Section
6.9. Sorting of Linked Lists
Section
6.10. Key-Indexed Counting
Chapter
7. Quicksort
Section
7.1. The Basic Algorithm
Section
7.2. Performance Characteristics of Quicksort
Section
7.3. Stack Size
Section
7.4. Small Subfiles
Section
7.5. Median-of-Three Partitioning
Section
7.6. Duplicate Keys
Section
7.7. Strings and Vectors
Section
7.8. Selection
Chapter
8. Merging and Mergesort
Section
8.1. Two-Way Merging
Section
8.2. Abstract In-Place Merge
Section
8.3. Top-Down Mergesort
Section
8.4. Improvements to the Basic Algorithm
Section
8.5. Bottom-Up Mergesort
Section
8.6. Performance Characteristics of Mergesort
Section
8.7. Linked-List Implementations of Mergesort
Section
8.8. Recursion Revisited
Chapter
9. Priority Queues and Heapsort
Exercises
Section
9.1. Elementary Implementations
Section
9.2. Heap Data Structure
Section
9.3. Algorithms on Heaps
Section
9.4. Heapsort
Section
9.5. Priority-Queue ADT
Section
9.6. Priority Queues for Client Arrays
Section
9.7. Binomial Queues
Chapter
10. Radix Sorting
Section
10.1. Bits, Bytes, and Words
Section
10.2. Binary Quicksort
Section
10.3. MSD Radix Sort
Section
10.4. Three-Way Radix Quicksort
Section
10.5. LSD Radix Sort
Section
10.6. Performance Characteristics of Radix Sorts
Section
10.7. Sublinear-Time Sorts
Chapter
11. Special-Purpose Sorting Methods
Section
11.1. Batcher's Odd–Even Mergesort
Section
11.2. Sorting Networks
Section
11.3. Sorting In Place
Section
11.4. External Sorting
Section
11.5. Sort–Merge Implementations
Section
11.6. Parallel Sort–Merge
References
for Part Three
Part
IV: Searching
Chapter
12. Symbol Tables and Binary Search Trees
Section
12.1. Symbol-Table Abstract Data Type
Section
12.2. Key-Indexed Search
Section
12.3. Sequential Search
Section
12.4. Binary Search
Section
12.5. Index Implementations with Symbol Tables
Section
12.6. Binary Search Trees
Section
12.7. Performance Characteristics of BSTs
Section
12.8. Insertion at the Root in BSTs
Section
12.9. BST Implementations of Other ADT Operations
Chapter
13. Balanced Trees
Exercises
Section
13.1. Randomized BSTs
Section
13.2. Splay BSTs
Section
13.3. Top-Down 2-3-4 Trees
Section
13.4. Red–Black Trees
Section
13.5. Skip Lists
Section
13.6. Performance Characteristics
Chapter
14. Hashing
Section
14.1. Hash Functions
Section
14.2. Separate Chaining
Section
14.3. Linear Probing
Section
14.4. Double Hashing
Section
14.5. Dynamic Hash Tables
Section
14.6. Perspective
Chapter
15. Radix Search
Section
15.1. Digital Search Trees
Section
15.2. Tries
Section
15.3. Patricia Tries
Section
15.4. Multiway Tries and TSTs
Section
15.5. Text-String–Index Algorithms
Chapter
16. External Searching
Section
16.1. Rules of the Game
Section
16.2. Indexed Sequential Access
Section
16.3. B Trees
Section
16.4. Extendible Hashing
Section
16.5. Perspective
References
for Part Four
