| |
| |
| Preface | |
| |
| |
| |
| Introduction | |
| |
| |
| The notion of algorithm | |
| |
| |
| Fundamentals of algorithmic problem solving | |
| |
| |
| Important problem types | |
| |
| |
| Fundamental data structures | |
| |
| |
| |
| Fundamentals of the Analysis of Algorithm Efficiency | |
| |
| |
| Analysis framework | |
| |
| |
| Asymptotic notations and standard efficiency classes | |
| |
| |
| Mathematical analysis of nonrecursive algorithms | |
| |
| |
| Mathematical analysis of recursive algorithms | |
| |
| |
| Example: Fibonacci numbers | |
| |
| |
| Empirical analysis of algorithms | |
| |
| |
| Algorithm visualization | |
| |
| |
| |
| Brute Force | |
| |
| |
| Selection sort and bubble sort | |
| |
| |
| Sequential search and brute-force string matching | |
| |
| |
| The closest-pair and convex-hull problems by brute force | |
| |
| |
| Exhaustive search | |
| |
| |
| |
| Divide-and-Conquer | |
| |
| |
| Mergesort | |
| |
| |
| Quicksort | |
| |
| |
| Binary search | |
| |
| |
| Binary tree traversals and related properties | |
| |
| |
| Multiplication of large integers and Strassen's matrix multiplication | |
| |
| |
| Closest-pair and convex-hull problems by divide-and-conquer | |
| |
| |
| |
| Decrease-and-Conquer | |
| |
| |
| Insertion sort | |
| |
| |
| Depth-first search and breadth-first search | |
| |
| |
| Topological sorting | |
| |
| |
| Algorithms for generating combinatorial objects | |
| |
| |
| Decrease-by-a-constant-factor algorithms | |
| |
| |
| Variable-size-decrease algorithms | |
| |
| |
| |
| Transform-and-conquer | |
| |
| |
| Presorting | |
| |
| |
| Gaussian elimination | |
| |
| |
| Balanced search trees | |
| |
| |
| Heaps and heapsort | |
| |
| |
| Horner's rule and binary exponentiation | |
| |
| |
| Problem reduction | |
| |
| |
| |
| Space and Time Tradeoffs | |
| |
| |
| Sorting by counting | |
| |
| |
| Horspool's and Boyer-Moore algorithms for string matching | |
| |
| |
| Hashing | |
| |
| |
| B-trees | |
| |
| |
| |
| Dynamic Programming | |
| |
| |
| Computing a binomial coefficient | |
| |
| |
| Shortest-path problems | |
| |
| |
| Warshall's and Floyd's algorithms | |
| |
| |
| Optimal binary search trees | |
| |
| |
| The knapsack problem and memory functions | |
| |
| |
| |
| Greedy Technique | |
| |
| |
| Prim's algorithm | |
| |
| |
| Kruskal's algorithm | |
| |
| |
| Dijkstra's algorithm | |
| |
| |
| Huffman trees | |
| |
| |
| |
| Limitations of Algorithm Power | |
| |
| |
| Lower-bound arguments | |
| |
| |
| Decision trees | |
| |
| |
| P, NP, and NP-complete problems | |
| |
| |
| Challenges of numerical algorithms | |
| |
| |
| |
| Coping with the Limitations of Algorithm Power | |
| |
| |
| Backtracking | |
| |
| |
| Branch-and-bound | |
| |
| |
| Approximation algorithms for NP-hard problems | |
| |
| |
| Algorithms for solving nonlinear equations | |
| |
| |
| Epilogue | |
| |
| |
| |
| Useful Formulas for the Analysis of Algorithms | |
| |
| |
| |
| Short Tutorial on Recurrence Relations | |
| |
| |
| Bibliography | |
| |
| |
| Hints to Exercises | |
| |
| |
| Index | |