Preface |
Foundations / I: |
Introduction |
The Role of Algorithms in Computing / 1: |
Algorithms / 1.1: |
Algorithms as a technology / 1.2: |
Getting Started / 2: |
Insertion sort / 2.1: |
Analyzing algorithms / 2.2: |
Designing algorithms / 2.3: |
Growth of Functions / 3: |
Asymptotic notation / 3.1: |
Standard notations and common functions / 3.2: |
Divide-and-Conquer / 4: |
The maximum-subarray problem / 4.1: |
Strassen's algorithm for matrix multiplication / 4.2: |
The substitution method for solving recurrences / 4.3: |
The recursion-tree method for solving recurrences / 4.4: |
The master method for solving recurrences / 4.5: |
Proof of the master theorem / 4.6: |
Probabilistic Analysis and Randomized Algorithms / 5: |
The hiring problem / 5.1: |
Indicator random variables / 5.2: |
Randomized algorithms / 5.3: |
Probabilistic analysis and further uses of indicator random variables / 5.4: |
Sorting and Order Statistics / II: |
Heapsort / 6: |
Heaps / 6.1: |
Maintaining the heap property / 6.2: |
Building a heap / 6.3: |
The heapsort algorithm / 6.4: |
Priority queues / 6.5: |
Quicksort / 7: |
Description of quicksort / 7.1: |
Performance of quicksort / 7.2: |
A randomized version of quicksort / 7.3: |
Analysis of quicksort / 7.4: |
Sorting in Linear Time / 8: |
Lower bounds for sorting / 8.1: |
Counting sort / 8.2: |
Radix sort / 8.3: |
Bucket sort / 8.4: |
Medians and Order Statistics / 9: |
Minimum and maximum / 9.1: |
Selection in expected linear time / 9.2: |
Selection in worst-case linear time / 9.3: |
Data Structures / III: |
Elementary Data Structures / 10: |
Stacks and queues / 10.1: |
Linked lists / 10.2: |
Implementing pointers and objects / 10.3: |
Representing rooted trees / 10.4: |
Hash Tables / 11: |
Direct-address tables / 11.1: |
Hash tables / 11.2: |
Hash functions / 11.3: |
Open addressing / 11.4: |
Perfect hashing / 11.5: |
Binary Search Trees / 12: |
What is a binary search tree? / 12.1: |
Querying a binary search tree / 12.2: |
Insertion and deletion / 12.3: |
Randomly built binary search trees / 12.4: |
Red-Black Trees / 13: |
Properties of red-black trees / 13.1: |
Rotations / 13.2: |
Insertion / 13.3: |
Deletion / 13.4: |
Augmenting Data Structures / 14: |
Dynamic order statistics / 14.1: |
How to augment a data structure / 14.2: |
Interval trees / 14.3: |
Advanced Design and Analysis Techniques / IV: |
Dynamic Programming / 15: |
Rod cutting / 15.1: |
Matrix-chain multiplication / 15.2: |
Elements of dynamic programming / 15.3: |
Longest common subsequence / 15.4: |
Optimal binary search trees / 15.5: |
Greedy Algorithms / 16: |
An activity-selection problem / 16.1: |
Elements of the greedy strategy / 16.2: |
Huffman codes / 16.3: |
Matroids and greedy methods / 16.4: |
A task-scheduling problem as a matroid / 16.5: |
Amortized Analysis / 17: |
Aggregate analysis / 17.1: |
The accounting method / 17.2: |
The potential method / 17.3: |
Dynamic tables / 17.4: |
Advanced Data Structures / V: |
B-Trees / 18: |
Definition of B-trees / 18.1: |
Basic operations on B-trees / 18.2: |
Deleting a key from a B-tree / 18.3: |
Fibonacci Heaps / 19: |
Structure of Fibonacci heaps / 19.1: |
Mergeable-heap operations / 19.2: |
Decreasing a key and deleting a node / 19.3: |
Bounding the maximum degree / 19.4: |
van Emde Boas Trees / 20: |
Preliminary approaches / 20.1: |
A recursive structure / 20.2: |
The van Emde Boas tree / 20.3: |
Data Structures for Disjoint Sets / 21: |
Disjoint-set operations / 21.1: |
Linked-list representation of disjoint sets / 21.2: |
Disjoint-set forests / 21.3: |
Analysis of union by rank with path compression / 21.4: |
Graph Algorithms / VI: |
Elementary Graph Algorithms / 22: |
Representations of graphs / 22.1: |
Breadth-first search / 22.2: |
Depth-first search / 22.3: |
Topological sort / 22.4: |
Strongly connected components / 22.5: |
Minimum Spanning Trees / 23: |
Growing a minimum spanning tree / 23.1: |
The algorithms of Kruskal and Prim / 23.2: |
Single-Source Shortest Paths / 24: |
The Bellman-Ford algorithm / 24.1: |
Single-source shortest paths in directed acyclic graphs / 24.2: |
Dijkstra's algorithm / 24.3: |
Difference constraints and shortest paths / 24.4: |
Proofs of shortest-paths properties / 24.5: |
All-Pairs Shortest Paths / 25: |
Shortest paths and matrix multiplication / 25.1: |
The Floyd-Warshall algorithm / 25.2: |
Johnson's algorithm for sparse graphs / 25.3: |
Maximum Flow / 26: |
Flow networks / 26.1: |
The Ford-Fulkerson method / 26.2: |
Maximum bipartite matching / 26.3: |
Push-relabel algorithms / 26.4: |
The relabel-to-front algorithm / 26.5: |
Selected Topics / VII: |
Multithreaded Algorithms / 27: |
The basics of dynamic multithreading / 27.1: |
Multithreaded matrix multiplication / 27.2: |
Multithreaded merge sort / 27.3: |
Matrix Operations / 28: |
Solving systems of linear equations / 28.1: |
Inverting matrices / 28.2: |
Symmetric positive-definite matrices and least-squares approximation / 28.3: |
Linear Programming / 29: |
Standard and slack forms / 29.1: |
Formulating problems as linear programs / 29.2: |
The simplex algorithm / 29.3: |
Duality / 29.4: |
The initial basic feasible solution / 29.5: |
Polynomials and the FFT / 30: |
Representing polynomials / 30.1: |
The DFT and FFT / 30.2: |
Efficient FFT implementations / 30.3: |
Number-Theoretic Algorithms / 31: |
Elementary number-theoretic notions / 31.1: |
Greatest common divisor / 31.2: |
Modular arithmetic / 31.3: |
Solving modular linear equations / 31.4: |
The Chinese remainder theorem / 31.5: |
Powers of an element / 31.6: |
The RSA public-key cryptosystem / 31.7: |
Primality testing / 31.8: |
Integer factorization / 31.9: |
String Matching / 32: |
The naive string-matching algorithm / 32.1: |
The Rabin-Karp algorithm / 32.2: |
String matching with finite automata / 32.3: |
The Knuth-Morris-Pratt algorithm / 32.4: |
Computational Geometry / 33: |
Line-segment properties / 33.1: |
Determining whether any pair of segments intersects / 33.2: |
Finding the convex hull / 33.3: |
Finding the closest pair of points / 33.4: |
NP-Completeness / 34: |
Polynomial time / 34.1: |
Polynomial-time verification / 34.2: |
NP-completeness and reducibility / 34.3: |
NP-completeness proofs / 34.4: |
NP-complete problems / 34.5: |
Approximation Algorithms / 35: |
The vertex-cover problem / 35.1: |
The traveling-salesman problem / 35.2: |
The set-covering problem / 35.3: |
Randomization and linear programming / 35.4: |
The subset-sum problem / 35.5: |
Appendix: Mathematical Background / VIII: |
Summations / A: |
Summation formulas and properties / A.1: |
Bounding summations / A.2: |
Sets, Etc. / B: |
Sets / B.1: |
Relations / B.2: |
Functions / B.3: |
Graphs / B.4: |
Trees / B.5: |
Counting and Probability / C: |
Counting / C.1: |
Probability / C.2: |
Discrete random variables / C.3: |
The geometric and binomial distributions / C.4: |
The tails of the binomial distribution / C.5: |
Matrices / D: |
Matrices and matrix operations / D.1: |
Basic matrix properties / D.2: |
Bibliography |
Index |
Preface |
Foundations / I: |
Introduction |
The Role of Algorithms in Computing / 1: |
Algorithms / 1.1: |
Algorithms as a technology / 1.2: |