| |
| |
| Preface | |
| |
| |
| |
| Foundations | |
| |
| |
| Introduction | |
| |
| |
| |
| The Role of Algorithms in Computing | |
| |
| |
| |
| Algorithms | |
| |
| |
| |
| Algorithms as a technology | |
| |
| |
| |
| Getting Started | |
| |
| |
| |
| Insertion sort | |
| |
| |
| |
| Analyzing algorithms | |
| |
| |
| |
| Designing algorithms | |
| |
| |
| |
| Growth of Functions | |
| |
| |
| |
| Asymptotic notation | |
| |
| |
| |
| Standard notations and common functions | |
| |
| |
| |
| Divide-and-Conquer | |
| |
| |
| |
| The maximum-subarray problem | |
| |
| |
| |
| Strassen's algorithm for matrix multiplication | |
| |
| |
| |
| The substitution method for solving recurrences | |
| |
| |
| |
| The recursion-tree method for solving recurrences | |
| |
| |
| |
| The master method for solving recurrences | |
| |
| |
| |
| Proof of the master theorem | |
| |
| |
| |
| Probabilistic Analysis and Randomized Algorithms | |
| |
| |
| |
| The hiring problem | |
| |
| |
| |
| Indicator random variables | |
| |
| |
| |
| Randomized algorithms | |
| |
| |
| |
| Probabilistic analysis and further uses of indicator random variables | |
| |
| |
| |
| Sorting and Order Statistics | |
| |
| |
| Introduction | |
| |
| |
| |
| Heapsort | |
| |
| |
| |
| Heaps | |
| |
| |
| |
| Maintaining the heap property | |
| |
| |
| |
| Building a heap | |
| |
| |
| |
| The heapsort algorithm | |
| |
| |
| |
| Priority queues | |
| |
| |
| |
| Quicksort | |
| |
| |
| |
| Description of quicksort | |
| |
| |
| |
| Performance of quicksort | |
| |
| |
| |
| A randomized version of quicksort | |
| |
| |
| |
| Analysis of quicksort | |
| |
| |
| |
| Sorting in Linear Time | |
| |
| |
| |
| Lower bounds for sorting | |
| |
| |
| |
| Counting sort | |
| |
| |
| |
| Radix sort | |
| |
| |
| |
| Bucket sort | |
| |
| |
| |
| Medians and Order Statistics | |
| |
| |
| |
| Minimum and maximum | |
| |
| |
| |
| Selection in expected linear time | |
| |
| |
| |
| Selection in worst-case linear time | |
| |
| |
| |
| Data Structures | |
| |
| |
| Introduction | |
| |
| |
| |
| Elementary Data Structures | |
| |
| |
| |
| Stacks and queues | |
| |
| |
| |
| Linked lists | |
| |
| |
| |
| Implementing pointers and objects | |
| |
| |
| |
| Representing rooted trees | |
| |
| |
| |
| Hash Tables | |
| |
| |
| |
| Direct-address tables | |
| |
| |
| |
| Hash tables | |
| |
| |
| |
| Hash functions | |
| |
| |
| |
| Open addressing | |
| |
| |
| |
| Perfect hashing | |
| |
| |
| |
| Binary Search Trees | |
| |
| |
| |
| What is a binary search tree? | |
| |
| |
| |
| Querying a binary search tree | |
| |
| |
| |
| Insertion and deletion | |
| |
| |
| |
| Randomly built binary search trees | |
| |
| |
| |
| Red-Black Trees | |
| |
| |
| |
| Properties of red-black trees | |
| |
| |
| |
| Rotations | |
| |
| |
| |
| Insertion | |
| |
| |
| |
| Deletion | |
| |
| |
| |
| Augmenting Data Structures | |
| |
| |
| |
| Dynamic order statistics | |
| |
| |
| |
| How to augment a data structure | |
| |
| |
| |
| Interval trees | |
| |
| |
| |
| Advanced Design and Analysis Techniques | |
| |
| |
| Introduction | |
| |
| |
| |
| Dynamic Programming | |
| |
| |
| |
| Rod cutting | |
| |
| |
| |
| Matrix-chain multiplication | |
| |
| |
| |
| Elements of dynamic programming | |
| |
| |
| |
| Longest common subsequence | |
| |
| |
| |
| Optimal binary search trees | |
| |
| |
| |
| Greedy Algorithms | |
| |
| |
| |
| An activity-selection problem | |
| |
| |
| |
| Elements of the greedy strategy | |
| |
| |
| |
| Huffman codes | |
| |
| |
| |
| Matroids and greedy methods | |
| |
| |
| |
| A task-scheduling problem as a matroid | |
| |
| |
| |
| Amortized Analysis | |
| |
| |
| |
| Aggregate analysis | |
| |
| |
| |
| The accounting method | |
| |
| |
| |
| The potential method | |
| |
| |
| |
| Dynamic tables | |
| |
| |
| |
| Advanced Data Structures | |
| |
| |
| Introduction | |
| |
| |
| |
| B-Trees | |
| |
| |
| |
| Definition of B-trees | |
| |
| |
| |
| Basic operations on B-trees | |
| |
| |
| |
| Deleting a key from a B-tree | |
| |
| |
| |
| Fibonacci Heaps | |
| |
| |
| |
| Structure of Fibonacci heaps | |
| |
| |
| |
| Mergeable-heap operations | |
| |
| |
| |
| Decreasing a key and deleting a node | |
| |
| |
| |
| Bounding the maximum degree | |
| |
| |
| |
| van Emde Boas Trees | |
| |
| |
| |
| Preliminary approaches | |
| |
| |
| |
| A recursive structure | |
| |
| |
| |
| The van Emde Boas tree | |
| |
| |
| |
| Data Structures for Disjoint Sets | |
| |
| |
| |
| Disjoint-set operations | |
| |
| |
| |
| Linked-list representation of disjoint sets | |
| |
| |
| |
| Disjoint-set forests | |
| |
| |
| |
| Analysis of union by rank with path compression | |
| |
| |
| |
| Graph Algorithms | |
| |
| |
| Introduction | |
| |
| |
| |
| Elementary Graph Algorithms | |
| |
| |
| |
| Representations of graphs | |
| |
| |
| |
| Breadth-first search | |
| |
| |
| |
| Depth-first search | |
| |
| |
| |
| Topological sort | |
| |
| |
| |
| Strongly connected components | |
| |
| |
| |
| Minimum Spanning Trees | |
| |
| |
| |
| Growing a minimum spanning tree | |
| |
| |
| |
| The algorithms of Kruskal and Prim | |
| |
| |
| |
| Single-Source Shortest Paths | |
| |
| |
| |
| The Bellman-Ford algorithm | |
| |
| |
| |
| Single-source shortest paths in directed acyclic graphs | |
| |
| |
| |
| Dijkstra's algorithm | |
| |
| |
| |
| Difference constraints and shortest paths | |
| |
| |
| |
| Proofs of shortest-paths properties | |
| |
| |
| |
| All-Pairs Shortest Paths | |
| |
| |
| |
| Shortest paths and matrix multiplication | |
| |
| |
| |
| The Floyd-Warshall algorithm | |
| |
| |
| |
| Johnson's algorithm for sparse graphs | |
| |
| |
| |
| Maximum Flow | |
| |
| |
| |
| Flow networks | |
| |
| |
| |
| The Ford-Fulkerson method | |
| |
| |
| |
| Maximum bipartite matching | |
| |
| |
| |
| Push-relabel algorithms | |
| |
| |
| |
| The relabel-to-front algorithm | |
| |
| |
| |
| Selected Topics | |
| |
| |
| Introduction | |
| |
| |
| |
| Multithreaded Algorithms | |
| |
| |
| |
| The basics of dynamic multithreading | |
| |
| |
| |
| Multithreaded matrix multiplication | |
| |
| |
| |
| Multithreaded merge sort | |
| |
| |
| |
| Matrix Operations | |
| |
| |
| |
| Solving systems of linear equations | |
| |
| |
| |
| Inverting matrices | |
| |
| |
| |
| Symmetric positive-definite matrices and least-squares approximation | |
| |
| |
| |
| Linear Programming | |
| |
| |
| |
| Standard and slack forms | |
| |
| |
| |
| Formulating problems as linear programs | |
| |
| |
| |
| The simplex algorithm | |
| |
| |
| |
| Duality | |
| |
| |
| |
| The initial basic feasible solution | |
| |
| |
| |
| Polynomials and the FFT | |
| |
| |
| |
| Representing polynomials | |
| |
| |
| |
| The DFT and FFT | |
| |
| |
| |
| Efficient FFT implementations | |
| |
| |
| |
| Number-Theoretic Algorithms | |
| |
| |
| |
| Elementary number-theoretic notions | |
| |
| |
| |
| Greatest common divisor | |
| |
| |
| |
| Modular arithmetic | |
| |
| |
| |
| Solving modular linear equations | |
| |
| |
| |
| The Chinese remainder theorem | |
| |
| |
| |
| Powers of an element | |
| |
| |
| |
| The RSA public-key cryptosystem | |
| |
| |
| |
| Primality testing | |
| |
| |
| |
| Integer factorization | |
| |
| |
| |
| String Matching | |
| |
| |
| |
| The naive string-matching algorithm | |
| |
| |
| |
| The Rabin-Karp algorithm | |
| |
| |
| |
| String matching with finite automata | |
| |
| |
| |
| The Knuth-Morris-Pratt algorithm | |
| |
| |
| |
| Computational Geometry | |
| |
| |
| |
| Line-segment properties | |
| |
| |
| |
| Determining whether any pair of segments intersects | |
| |
| |
| |
| Finding the convex hull | |
| |
| |
| |
| Finding the closest pair of points | |
| |
| |
| |
| NP-Completeness | |
| |
| |
| |
| Polynomial time | |
| |
| |
| |
| Polynomial-time verification | |
| |
| |
| |
| NP-completeness and reducibility | |
| |
| |
| |
| NP-completeness proofs | |
| |
| |
| |
| NP-complete problems | |
| |
| |
| |
| Approximation Algorithms | |
| |
| |
| |
| The vertex-cover problem | |
| |
| |
| |
| The traveling-salesman problem | |
| |
| |
| |
| The set-covering problem | |
| |
| |
| |
| Randomization and linear programming | |
| |
| |
| |
| The subset-sum problem | |
| |
| |
| |
| Appendix: Mathematical Background | |
| |
| |
| Introduction | |
| |
| |
| |
| Summations | |
| |
| |
| |
| Summation formulas and properties | |
| |
| |
| |
| Bounding summations | |
| |
| |
| |
| Sets, Etc. | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Relations | |
| |
| |
| |
| Functions | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Counting and Probability | |
| |
| |
| |
| Counting | |
| |
| |
| |
| Probability | |
| |
| |
| |
| Discrete random variables | |
| |
| |
| |
| The geometric and binomial distributions | |
| |
| |
| |
| The tails of the binomial distribution | |
| |
| |
| |
| Matrices | |
| |
| |
| |
| Matrices and matrix operations | |
| |
| |
| |
| Basic matrix properties | |
| |
| |
| Bibliography | |
| |
| |
| Index | |