Sitemap
Introduction to Algorithms, Second Edition
Changes for the second edition
Acknowledgments for the first edition
Acknowledgments for the second edition
Chapter 1: The Role of Algorithms in Computing
1.2 Algorithms as a technology
Chapter 3: Growth of Functions
3.2 Standard notations and common functions
4.4: Proof of the master theorem
Chapter 5: Probabilistic Analysis and Randomized Algorithms
5.2 Indicator random variables
5.4 Probabilistic analysis and further uses of indicator random variables
Part II: Sorting and Order Statistics
6.2 Maintaining the heap property
7.3 A randomized version of quicksort
Chapter 8: Sorting in Linear Time
Chapter 9: Medians and Order Statistics
9.2 Selection in expected linear time
9.3 Selection in worst-case linear time
Chapter 10: Elementary Data Structures
10.3 Implementing pointers and objects
10.4 Representing rooted trees
Chapter 12: Binary Search Trees
12.1 What is a binary search tree?
12.2 Querying a binary search tree
12.4 Randomly built binary search trees
Chapter 14: Augmenting Data Structures
14.2 How to Augment a Data Structure
Part IV: Advanced Design and Analysis Techniques
Chapter 15: Dynamic Programming
15.2 Matrix-chain multiplication
15.3 Elements of dynamic programming
15.4 Longest common subsequence
15.5 Optimal binary search trees
16.1 An activity-selection problem
16.2 Elements of the greedy strategy
16.4 Theoretical foundations for greedy methods
16.5 A task-scheduling problem
Chapter 17: Amortized Analysis
Part V: Advanced Data Structures
Data structures on secondary storage
18.2 Basic operations on B-trees
18.3 Deleting a key from a B-tree
19.1 Binomial trees and binomial heaps
19.2 Operations on binomial heaps
20.1 Structure of Fibonacci heaps
20.2 Mergeable-heap operations
20.3 Decreasing a key and deleting a node
20.4 Bounding the maximum degree
Chapter 21: Data Structures for Disjoint Sets
21.2 Linked-list representation of disjoint sets
21.4 Analysis of union by rank with path compression
Chapter 22: Elementary Graph Algorithms
22.5 Strongly connected components
Chapter 23: Minimum Spanning Trees
23.1 Growing a minimum spanning tree
23.2 The algorithms of Kruskal and Prim
Chapter 24: Single-Source Shortest Paths
Optimal substructure of a shortest path
Properties of shortest paths and relaxation
24.1 The Bellman-Ford algorithm
24.2 Single-source shortest paths in directed acyclic graphs
24.4 Difference constraints and shortest paths
24.5 Proofs of shortest-paths properties
Chapter 25: All-Pairs Shortest Paths
25.1 Shortest paths and matrix multiplication
25.2 The Floyd-Warshall algorithm
25.3 Johnson''s algorithm for sparse graphs
26.2 The Ford-Fulkerson method
26.3 Maximum bipartite matching
26.5 The relabel-to-front algorithm
27.3 A bitonic sorting network
28.2 Strassen''s algorithm for matrix multiplication
28.3 Solving systems of linear equations
28.5 Symmetric positive-definite matrices and least-squares approximation
Chapter 29: Linear Programming
An overview of linear programming
Applications of linear programming
Algorithms for linear programming
29.2 Formulating problems as linear programs
29.5 The initial basic feasible solution
Chapter 30: Polynomials and the FFT
30.1 Representation of polynomials
30.3 Efficient FFT implementations
Chapter 31: Number-Theoretic Algorithms
31.1 Elementary number-theoretic notions
31.4 Solving modular linear equations
31.5 The Chinese remainder theorem
31.7 The RSA public-key cryptosystem
32.1 The naive string-matching algorithm
32.3 String matching with finite automata
32.4 The Knuth-Morris-Pratt algorithm
Chapter 33: Computational Geometry
33.2 Determining whether any pair of segments intersects
33.4 Finding the closest pair of points
NP-completeness and the classes P and NP
Overview of showing problems to be NP-complete
Decision problems vs. optimization problems
34.2 Polynomial-time verification
34.3 NP-completeness and reducibility
Chapter 35: Approximation Algorithms
35.2 The traveling-salesman problem
35.4 Randomization and linear programming
Part VIII: Appendix: Mathematical Background
A.1 Summation formulas and properties
Appendix C: Counting and Probability
C.4 The geometric and binomial distributions
C.5 The tails of the binomial distribution