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