Introduction to Algorithms,
Second Edition (2001)
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
Contents
Prefacexiii
I Foundations
Introduction3
1The Role of Algorithms in Computing5NEW!
1.1Algorithms5
1.2Algorithms as technology10
2Getting Started15Chapter 2 now includes loop
2.1 Insertion sort15invariants & a greater discussion
2.2 Analyzing algorithms21of merge/sort
2.3 Designing Algorithms27
3Growth of Functions41
3.1 Asymptotic notation41
3.2Standard notations and common functions51
4Recurrences62
4.1 The substitution method 63
4.2 The recursion-tree method67Removed iteration method
4.3 The master method73
*4.4 Proof of the master theorem76
5 Probabilistic Analysis and Randomized Algorithms 91 NEW!
5.1The hiring problem91
5.2Indicator random variables94
5.3Randomized algorithms 99
*5.4Probabilistic analysis and further uses of indicator random variables 105
IISorting and Order Statistics
Introduction123
6Heapsort 127Added loop invariance;
6.1Heaps127clarified priority queues
6.2Maintaining the heap property130for min or max
6.3Building a heap132
6.4The heapsort algorithm135
6.5Priority queues138
7Quicksort145Chapter 7 has been
7.1Description of quicksort 145rewritten; analysis is
7.2Performance of quicksort149different; new partition
7.3Randomized versions of quicksort153procedure used
7.4Analysis of quicksort155
8Sorting in Linear Time 165Bucket sort analysis is
8.1 Lower bounds for sorting165different
8.2Counting sort168
8.3Radix sort170
8.4Bucket sort174
9Medians and Order Statistics1839.2 has been rewritten
9.1Minimum and maximum1849.3 has been rewritten and
9.2Selection in expected linear time185includes updated analysis
9.3Selection in worst-case linear time189
III Data Structures
Introduction197
10Elementary Data Structures200No changes to Chapter 10
10.1Stacks and queues200
10.2Linked lists204
10.3Implementing pointers and objects209
10.4Representing rooted trees214
11Hash Tables221
11.1Direct-address tables 222
11.2Hash tables224
11.3Hash functions229
11.4Open addressing237
*11.5Perfect Hashing245New section
12Binary Search Trees25312.4 has been rewritten and
12.1What is a binary search tree?253is now simpler
12.2Querying a binary search tree?256
12.3Insertion and deletion261
*12.4Randomly built binary search trees264
13 Red-Black Trees273Added loop invariant arguments
13.1Properties of red-black trees 273
13.2Rotations277
13.3Insertion280
13.4Deletion288
14Augmenting Data Structures302Added loop invariants
14.1Dynamic order statistics302
14.2How to augment a data structure308
14.3Interval trees 311
IV Advanced Design and Analysis Techniques
Introduction321
15Dynamic Programming 323Chapter 15 has been
15.1Assembly-line scheduling324rewritten and now
15.2Matrix-chain multiplication 331includes more discussion
15.3Elements of dynamic programming339on dynamic programming
15.4Longest common subsequence350
15.5Optimal binary search trees35615.5 replaces a section on
optimal polygon triangulation
16Greedy Algorithms 370
16.1An activity-selection problem371Chapter 16 has been
16.2Elements of the greedy strategy379rewritten to clarify key issues
16.3Huffman codes385
*16.4Theoretical foundations for greedy methods393
*16.5A task-scheduling problem399
17Amortized Analysis405
17.1Aggregate analysis40617.1 was called “aggregate
17.2The accounting method410method” in first edition
17.3The potential method412
17.4Dynamic tables416
V Advanced Data Structures
Introduction431
18B-Trees 434
18.1Definition of B-trees438
18.2Basic operations on B-trees441
18.3Deleting a key from a B-tree449
19 Binomial Heaps455Added loop invariants
19.1Binomial trees and binomial heaps457
19.2Operations on binomial heaps 461
20Fibonacci Heaps476
20.1Structure of Fibonacci heaps477
20.2Mergeable-heap operations479
20.3Decreasing a key and deleting a node489
20.4Bounding the maximum degree493
21Data Structures for Disjoint Sets49821.3 and 21.4 have
21.1Disjoint-set operations 498been rewritten
21.2Linked-list representation of disjoint sets501
21.3Disjoint-set forests501
*21.4Analysis of union by rank with path compression509
VI Graph Algorithms
Introduction525
22Elementary Graph Algorithms52722.5 has been rewritten
22.1Representations of graphs527
22.2Breadth-first search531
22.3Depth-first search540
22.4Topological sort 549
22.5Strongly connected components552
23Minimum Spanning Trees561Added loop invariants
23.1Growing a minimum spanning tree562
23.2The algorithms of Kruskal and Prim567
24Single-Source Shortest Paths580Chapter 24 has been reordered;
24.1The Bellman-Ford algorithm588more loop invariants used; 24.5
24.2Single-source shortest paths in directed acyclic graphs 592 is new
24.3Dijkstra’s algorithm595
24.4Difference constraints and shortest paths601
24.5Proofs of shortest-paths properties607
25All-Pairs Shortest Paths620
25.1Shortest paths and matrix multiplication622
25.2The Floyd-Warshall algorithm629
25.3Johnson’s algorithm for sparse graphs636
26Maximum Flow643
26.1Flow networks644
26.2The Ford-Fulkerson method651
26.3Maximum bipartite matching664
*26.4Push-relabel algorithms669Standard names now used
*26.5The relabel-to-front algorithm681in 26.4 and 26.5
VIISelected Topics
Introduction701
27Sorting Networks704
27.1Compression networks704
27.2The zero-one principle709
27.3A bitonic sorting network712
27.4A merging network716
27.5A sorting network719
28Matrix Operations725Was Chapter 31 in first edition;
28.1Properties of matrices725old section 31.3 has been deleted
28.2Strassen’s algorithm for matrix multiplication735
28.3Solving systems of linear equations 742
28.4Inverting matrices755
28.5Symmetric positive-definite matrices and least-squares
approximation760
29Linear Programming770
29.1Standard and slack forms777
29.2Formulating problems as linear programs785
29.3The simplex algorithm790
29.4Duality804
29.5The initial basic feasible solution811
30Polynomials and the FFT822
30.1Representation of polynomials824
30.2The DFT and FFT830
30.3Efficient FFT implementations839
31Number-Theoretic Algorithms849
31.1Elementary number theoretic notions850
31.2Greatest common divisor856
31.3Modular arithmetic862
31.4Solving modular linear equations869
31.5The Chinese remainder theorem873
31.6Powers of an element876
31.7The RSA public-key cryptosystem881
*31.8Primality testing887
*31.9Integer factorization896
32String Matching906Dropped section on Boyer-
32.1The naïve string-matching algorithm 848Moore
32.2The Rabin-Karp algorithm911
32.3String matching with finite automata916
32.4The Knuth-Morrisz-Pratt algorithm923
33Computational Geometry933
33.1Line-segment properties934Reworked 33.1
33.2Determining whether any pair of segments intersects 940
33.3Finding the convex hull947
33.4Finding the closest pair of points957
34NP-Completeness966Chapter 34 includes more
34.1Polynomial time971overview at beginning; 34.5
34.2Polynomial-time verification979has been rewritten and
34.3NP-completeness and reducibility984simplified
34.4NP-completeness proofs995
34.5NP-complete problems1003
35Approximation Algorithms1022
35.1The vertex-cover problem1024
35.2The traveling-salesman problem1027
35.3The set-covering problem1033
35.4Randomization and linear programming1039
35.5The subset-sum problem1043
VIIIAppendix: Mathematical Background
Introduction1057
ASummations1058
A.1Summation formulas and properties 1058
A.2Bounding summations1062
BSets, Etc.1070
B.1Sets1070
B.2Relations1075
B.3Functions1077
B.4Graphs1080
B.5Trees1085
CCounting and Probability1094Was Chapter 6 in first edition
C.1Counting1094
C.2Probability1100
C.3Discrete random variables1106
C.4The geometric and binomial distributions1112
*C.5The tails of the binomial distribution1118
Bibliography1127Updated
Index1145Created by Tom Cormen