Table of Contents
Preface vii
13 Introduction to Greedy Algorithms 1
13.1 The Greedy Algorithm Design Paradigm 1
13.2 A Scheduling Problem 4
13.3 Developing a Greedy Algorithm 6
13.4 Proof of Correctness 12
Problems 21
14 Huffman Codes 23
14.1 Codes 23
14.2 Codes as Trees 28
14.3 Huffman’s Greedy Algorithm 32
*14.4 Proof of Correctness 41
Problems 49
15 Minimum Spanning Trees 52
15.1 Problem Definition 52
15.2 Prim’s Algorithm 57
*15.3 Speeding Up Prim’s Algorithm via Heaps 62
*15.4 Prim’s Algorithm: Proof of Correctness 69
15.5 Kruskal’s Algorithm 76
*15.6 Speeding Up Kruskal’s Algorithm via Union-Find 81
*15.7 Kruskal’s Algorithm: Proof of Correctness 91
15.8 Application: Single-Link Clustering 94
Problems 99
16 Introduction to Dynamic Programming 103
16.1 The Weighted Independent Set Problem 104
16.2 A Linear-Time Algorithm for WIS in Paths 108
16.3 A Reconstruction Algorithm 116
16.4 The Principles of Dynamic Programming 118
16.5 The Knapsack Problem 123
Problems 133
17 Advanced Dynamic Programming 137
17.1 Sequence Alignment 137
*17.2 Optimal Binary Search Trees 148
Problems 163
18 Shortest Paths Revisited 167
18.1 Shortest Paths with Negative Edge Lengths 167
18.2 The Bellman-Ford Algorithm 172
18.3 The All-Pairs Shortest Path Problem 185
18.4 The Floyd-Warshall Algorithm 187
Problems 198
Epilogue: A Field Guide to Algorithm Design 201
Hints and Solutions to Selected Problems 203
Index 211
