Table of Contents

Algorithms

Richard Johnsonbaugh

Marcus Schaefer

Preface
  1. Introduction
    2.
    1.1. Algorithms
    1.2. Pseudocode for Algorithms
    1.3. The Present
    1.4. The Future
    Notes
    Chapter Exercises
  1. Mathematics for Algorithms
    2.
    2.1. Definitions, Notation, and Basic Results
    2.2. Mathematical Induction
    2.3. Analysis of Algorithms
    2.4. Recurrence Relations
    2.5. Graphs
    2.6. Trees
    Notes
    Chapter Exercises
  1. Data Structures
    2.
    3.1. Abstract Data Types
    3.2. Stacks and Queues
    3.3. Linked Lists
    3.4. Binary Trees
    3.5. Priority Queues, Binary Heaps, and Heapsort
    3.6. Disjoint Sets
    Notes
    Chapter Exercises
  1. Searching
    2.
    4.1. Binary Search
    4.2. Depth-First Search
    4.3. Breadth-First Search
    4.4. Topological Sort
    4.5. Backtracking
    Notes
    Chapter Exercises
  1. Divide and Conquer
    2.
    5.1. A Tiling Problem
    5.2. Mergesort
    5.3. Finding a Closest Pair of Points
    5.4. Strassen's Matrix Product Algorithm
    Notes
    Chapter Exercises
  1. Sorting and Selection
    2.
    6.1. Insertion Sort
    6.2. Quicksort
    6.3. A Lower Bound for the Sorting Problem
    6.4. Counting Sort and Radix Sort
    6.5. Selection
    Notes
    Chapter Exercises
  1. Greedy Algorithms
    2.
    7.1. Coin Changing
    7.2. Kruskal's Algorithm
    7.3. Prim's Algorithm
    7.4. Dijkstra's Algorithm
    7.5. Huffman Codes
    7.6. The Continuous Knapsack Problem
    Notes
    Chapter Exercises
  1. Dynamic Programming
    2.
    8.1. Computing Fibonacci Numbers
    8.2. Coin Changing Revisited
    8.3. Multiplying Matrices
    8.4. The Longest Common Subsequence Problem
    8.5. The Algorithms of Floyd and Warshall
    Notes
    Chapter Exercises
  1. Text Searching
    2.
    9.1. Simple Text Search
    9.2. The Rabin-Karp Algorithm
    9.3. The Knuth-Morris-Pratt Algorithm
    9.4. The Boyer-Moore-Horspool Algorithm
    9.5. Approximate Pattern Matching
    9.6. Regular Expression Matching
    Notes
    Chapter Exercises
  1. P and NP
    2.
    10.1. Polynomial Time
    10.2. Nondeterministic Algorithms and NP
    10.3. Reducibility and NP-Completeness
    10.4. NP-Complete Problems
    10.5. More on NP-Completeness
    Notes
    Chapter Exercises
  1. Coping with NP-Completeness
    2.
    11.1. Brute Force
    11.2. Randomness
    11.3. Approximation
    11.4. Parameterization
    11.5. Heuristics
    Notes
    Chapter Exercises
  1. Parallel and Distributed Algorithms
    2.
    12.1. Introduction
    12.2. The Parallel Random Access Machine (PRAM)
    12.3. Sorting Networks
    12.4. Parallel Architectures
    12.5. Distributed Algorithms
    Notes
    Chapter Exercises

References

Solutions to Selected Exercises

Index