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

Top Comments