| |

| |

| |

Algorithms: Efficiency, Analysis, and Order | |

| |

| |

| |

Algorithms | |

| |

| |

| |

The Importance of Developing Efficient Algorithms | |

| |

| |

| |

Sequential Search Versus Binary Search | |

| |

| |

| |

The Fibonacci Sequence | |

| |

| |

| |

Analysis of Algorithms | |

| |

| |

| |

Complexity Analysis | |

| |

| |

| |

Applying the Theory | |

| |

| |

| |

Analysis of Correctness | |

| |

| |

| |

Order | |

| |

| |

| |

An Intuitive Introduction to Order | |

| |

| |

| |

A Rigorous Introduction to Order | |

| |

| |

| |

Using a Limit to Determine Order | |

| |

| |

| |

Outline of This Book | |

| |

| |

Exercises | |

| |

| |

| |

Divide-and-Conquer | |

| |

| |

| |

Binary Search | |

| |

| |

| |

Mergesort | |

| |

| |

| |

The Divide-and-Conquer Approach | |

| |

| |

| |

Quicksort (Partition Exchange Sort) | |

| |

| |

| |

Strassen's Matrix Multiplication Algorithm | |

| |

| |

| |

Arithmetic with Large Numbers | |

| |

| |

| |

Representation of Large Integers: Addition and Other Linear-Time Operations | |

| |

| |

| |

Multiplication of Large Integers | |

| |

| |

| |

Determining Thresholds | |

| |

| |

| |

When Not to Use Divide-and-Conquer | |

| |

| |

Exercises | |

| |

| |

| |

Dynamic Programming | |

| |

| |

| |

The Binomial Coefficient | |

| |

| |

| |

Floyd's Algorithm for Shortest Paths | |

| |

| |

| |

Dynamic Programming and Optimization Problems | |

| |

| |

| |

Chained Matrix Multiplication | |

| |

| |

| |

Optimal Binary Search Trees | |

| |

| |

| |

The Traveling Salesperson Problem | |

| |

| |

| |

Sequence Alignment | |

| |

| |

Exercises | |

| |

| |

| |

The Greedy Approach | |

| |

| |

| |

Minimum Spanning Trees | |

| |

| |

| |

Prim's Algorithm | |

| |

| |

| |

Kruskal's Algorithm | |

| |

| |

| |

Comparing Prim's Algorithm with Kruskal's Algorithm | |

| |

| |

| |

Final Discussion | |

| |

| |

| |

Dijkstra's Algorithm for Single-Source Shortest Paths | |

| |

| |

| |

Scheduling | |

| |

| |

| |

Minimizing Total Time in the System | |

| |

| |

| |

Scheduling with Deadlines | |

| |

| |

| |

Huffman Code | |

| |

| |

| |

Prefix Codes | |

| |

| |

| |

Huffman's Algorithm | |

| |

| |

| |

The Greedy Approach Versus Dynamic Programming: The Knapsack Problem | |

| |

| |

| |

A Greedy Approach to the 0-1 Knapsack Problem | |

| |

| |

| |

A Greedy Approach to the Fractional Knapsack Problem | |

| |

| |

| |

A Dynamic Programming Approach to the 0-1 Knapsack Problem | |

| |

| |

| |

A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem | |

| |

| |

Exercises | |

| |

| |

| |

Backtracking | |

| |

| |

| |

The Backtracking Technique | |

| |

| |

| |

The n-Queens Problem | |

| |

| |

| |

Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm | |

| |

| |

| |

The Sum-of-Subsets Problem | |

| |

| |

| |

Graph Coloring | |

| |

| |

| |

The Hamiltonian Circuits Problem | |

| |

| |

| |

The 0-1 Knapsack Problem | |

| |

| |

| |

A Backtracking Algorithm for the 0-1 Knapsack Problem | |

| |

| |

| |

Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem | |

| |

| |

Exercises | |

| |

| |

| |

Branch-and-Bound | |

| |

| |

| |

Illustrating Branch-and-Bound with the 0-1 Knapsack Problem | |

| |

| |

| |

Breadth-First Search with Branch-and-Bound Pruning | |

| |

| |

| |

Best-First Search with Branch-and-Bound Pruning | |

| |

| |

| |

The Traveling Salesperson Problem | |

| |

| |

| |

Abductive Inference (Diagnosis) | |

| |

| |

Exercises | |

| |

| |

| |

Introduction to Computational Complexity: The Sorting Problem | |

| |

| |

| |

Computational Complexity | |

| |

| |

| |

Insertion Sort and Selection Sort | |

| |

| |

| |

Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison | |

| |

| |

| |

Mergesort Revisited | |

| |

| |

| |

Quicksort Revisited | |

| |

| |

| |

Heapsort | |

| |

| |

| |

Heaps and Basic Heap Routines | |

| |

| |

| |

An Implementation of Heapsort | |

| |

| |

| |

Comparison of Mergesort, Quicksort, and Heapsort | |

| |

| |

| |

Lower Bounds for Sorting Only by Comparison of Keys | |

| |

| |

| |

Decision Trees for Sorting Algorithms | |

| |

| |

| |

Lower Bounds for Worst-Case Behavior | |

| |

| |

| |

Lower Bounds for Average-Case Behavior | |

| |

| |

| |

Sorting by Distribution (Radix Sort) | |

| |

| |

Exercises | |

| |

| |

| |

More Computational Complexity: The Searching Problem | |

| |

| |

| |

Lower Bounds for Searching Only by Comparisons of Keys | |

| |

| |

| |

Lower Bounds for Worst-Case Behavior | |

| |

| |

| |

Lower Bounds for Average-Case Behavior | |

| |

| |

| |

Interpolation Search | |

| |

| |

| |

Searching in Trees | |

| |

| |

| |

Binary Search Trees | |

| |

| |

| |

B-Trees | |

| |

| |

| |

Hashing | |

| |

| |

| |

The Selection Problem: Introduction to Adversary Arguments | |

| |

| |

| |

Finding the Largest Key | |

| |

| |

| |

Finding Both the Smallest and Largest Keys | |

| |

| |

| |

Finding the Second-Largest Key | |

| |

| |

| |

Finding the kth-Smallest Key | |

| |

| |

| |

A Probabilistic Algorithm for the Selection Problem | |

| |

| |

Exercises | |

| |

| |

| |

Computational Complexity and intractability: An Introduction to the Theory of NP | |

| |

| |

| |

Intractability | |

| |

| |

| |

Input Size Revisited | |

| |

| |

| |

The Three General Problems | |

| |

| |

| |

Problems for Which Polynomial-Time Algorithms Have Been Found | |

| |

| |

| |

Problems That Have Been Proven to Be Intractable | |

| |

| |

| |

Problems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found | |

| |

| |

| |

The Theory of NP | |

| |

| |

| |

The Sets P and NP | |

| |

| |

| |

NP-Complete Problems | |

| |

| |

| |

NP-Hard, NP-Easy, and NP-Equivalent Problems | |

| |

| |

| |

Handling NP-Hard Problems | |

| |

| |

| |

An Approximation Algorithm for the Traveling Salesperson Problem | |

| |

| |

| |

An Approximation Algorithm for the Bin-Packing Problem | |

| |

| |

Exercises | |

| |

| |

| |

Number-Theoretic Algorithms | |

| |

| |

| |

Number Theory Review | |

| |

| |

| |

Composite and Prime Numbers | |

| |

| |

| |

Greatest Common Divisor | |

| |

| |

| |

Prime Factorization | |

| |

| |

| |

Least Common Multiple | |

| |

| |

| |

Computing the Greatest Common Divisor | |

| |

| |

| |

Euclid's Algorithm | |

| |

| |

| |

An Extension to Euclid's Algorithm | |

| |

| |

| |

Modular Arithmetic Review | |

| |

| |

| |

Group Theory | |

| |

| |

| |

Congruency Modulo n | |

| |

| |

| |

Subgroups | |

| |

| |

| |

Solving Modular Linear Equations | |

| |

| |

| |

Computing Modular Powers | |

| |

| |

| |

Finding Large Prime Numbers | |

| |

| |

| |

Searching for a Large Prime | |

| |

| |

| |

Checking if a Number Is Prime | |

| |

| |

| |

The RSA Public-Key Cryptosystem | |

| |

| |

| |

Public-Key Cryptosystems | |

| |

| |

| |

The RSA Cryptosystem | |

| |

| |

Exercises | |

| |

| |

| |

Introduction to Parallel Algorithms | |

| |

| |

| |

Parallel Architectures | |

| |

| |

| |

Control Mechanism | |

| |

| |

| |

Address-Space Organization | |

| |

| |

| |

Interconnection Networks | |

| |

| |

| |

The PRAM Model | |

| |

| |

| |

Designing Algorithms for the CREW PRAM Model | |

| |

| |

| |

Designing Algorithms for the CRCW PRAM Model | |

| |

| |

Exercises | |

| |

| |

| |

Review of Necessary Mathematics | |

| |

| |

| |

Notation | |

| |

| |

| |

Functions | |

| |

| |

| |

Mathematical Induction | |

| |

| |

| |

Theorems and Lemmas | |

| |

| |

| |

Logarithms | |

| |

| |

| |

Definition and Properties of Logarithms | |

| |

| |

| |

The Natural Logarithm | |

| |

| |

| |

Sets | |

| |

| |

| |

Permutations and Combinations | |

| |

| |

| |

Probability | |

| |

| |

| |

Randomness | |

| |

| |

| |

The Expected Value | |

| |

| |

Exercises | |

| |

| |

| |

Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms | |

| |

| |

| |

Solving Recurrences Using Induction | |

| |

| |

| |

Solving Recurrences Using the Characteristic Equation | |

| |

| |

| |

Homogeneous Linear Recurrences | |

| |

| |

| |

Nonhomogeneous Linear Recurrences | |

| |

| |

| |

Change of Variables (Domain Transformations) | |

| |

| |

| |

Solving Recurrences by Substitution | |

| |

| |

| |

Extending Results for n, a Power of a Positive Constant b, to n in General | |

| |

| |

| |

Proofs of Theorems | |

| |

| |

Exercises | |

| |

| |

| |

Data Structures for Disjoint Sets | |

| |

| |

References | |

| |

| |

Index | |