| |
| |
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 | |