Algorithms in Java, Parts 1-4 (3rd Edition) (Pts.1-4)

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