Table of Contents

Algorithms in Java: Parts 1-4, Third Edition

Copyright
Preface
    Scope
    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


Appendix
    Exercises

Top