Chapter 1 Design and Analysis of Algorithms 1
1.1 From Problems to Programs 1
1.2 Abstract Data Types 10
1.3 Data Types， Data Structures， and Abstract Data Types 13
1.4 The Running Time of a Program 16
1.5 Calculating the Running Time of a Program 21
1.6 Good Programming Practice 27
1.7 Super Pascal 29
Chapter 2 Basic Data Types 37
2.1 The Data Type “List 37
2.2 Implementation of Lists 40
2.3 Stacks 53
2.4 Queues 56
2.5 Mappings 61
2.6 Stacks and Recursive Procedures 64
Chapter 3 Trees 75
3.1 Basic Terminology 75
3.2 The ADT TREE 82
3.3 Implementations of Trees 84
3.4 Binary Trees 93
Chapter 4 Basic Operations on Sets 107
4.1 Introduction to Sets 107
4.2 An ADT with Union， Intersection， and Difference 109
4.3 A Bit-Vector Implementation of Sets 112
4.4 A Linked-List Implementation of Sets 115
4.5 The Dictionary 117
4.6 Simple Dictionary Implementations 119
4.7 The Hash Table Data Structure 122
4.8 Estimating the Efficiency of Hash Functions 129
4.9 Implementation of the Mapping ADT 135
4.10 Priority Queues 135
4.11 Implementations of Priority Queues 138
4.12 Some Complex Set Structures 145
Chapter 5 Advanced Set Representation Methods 155
5.1 Binary Search Trees 155
5.2 Time Analysis of Binary Search Tree Operations 160
5.3 Tries 163
5.4 Balanced Tree Implementations of Sets 169
5.5 Sets with the MERGE and FIND Operations 180
5.6 An ADT with MERGE and SPLIT 189
Chapter 6 Directed Graphs 198
6.1 Basic Definitions 198
6.2 Representations for Directed Graphs 199
6.3 The Single-Source Shortest Paths Problem 203
6.4 The All-Pairs Shortest Path Problem 208
6.5 Traversals of Directed Graphs 215
6.6 Directed Acyclic Graphs 219
6.7 Strong Components 222
Chapter 7 Undirected Graphs 230
7.1 Definitions 230
7.2 Minimum-Cost Spanning Trees 233
7.3 Traversals 239
7.4 Articulation Points and Biconnected Components 244
7.5 Graph Matching 246
Chapter 8 Sorting 253
8.1 The Internal Sorting Model 253
8.2 Some Simple Sorting Schemes 254
8.3 Quicksort 260
8.4 Heapsort 271
8.5 Bin Sorting 274
8.6 A Lower Bound for Sorting by Comparisons 282
8.7 Order Statistics 286
Chapter 9 Algorithm Analysis Techniques 293
9.1 Efficiency of Algorithms 293
9.2 Analysis of Recursive Programs 294
9.3 Solving Recurrence Equations 296
9.4 A General Solution for a Large Class of Recurrences 298
Chapter 10 Algorithm Design Techniques 306
10.1 Divide-and-Conquer Algorithms 306
10.2 Dynamic Programming 311
10.3 Greedy Algorithms 321
10.4 Backtracking 324
10.5 Local Search Algorithms 336
Chapter 11 Data Structures and Algorithms for External Storage 347
11.1 A Model of External Computation 347
11.2 External Sorting 349
11.3 Storing Information in Files 361
11.4 External Search Trees 368
Chapter 12 Memory Management 378
12.1 The Issues in Memory Management 378
12.2 Managing Equal-Sized Blocks 382
12.3 Garbage Collection Algorithms for Equal-Sized Blocks 384
12.4 Storage Allocation for Objects with Mixed Sizes 392
12.5 Buddy Systems 400
12.6 Storage Compaction 404
Bibliography 411
Index 419