Introduction to Algorithms

Thomas H. Cormen is Emeritus Professor of Computer Science at Dartmouth College. Charles E. Leiserson is Edwin Sibley Webster Professor in Electrical Engineering and Computer Science at MIT. Ronald L. Rivest is Institute Professor at MIT. Clifford Stein is Wai T. Chang Professor of Industrial Engineering and Operations Research, and of Computer Science at Columbia University.

"The leading introductory textbook and reference on algorithms"--

Preface xiiiI FoundationsIntroduction 31 The Role of Algorithms in Computing 52 Getting Started 173 Characterizing Running Times 494 Divide-and-Conquer 765 Probabilistic Analysis and Randomized Algorithms 126II Sorting and Order Statistics Introduction 1576 Heapsort 1617 Quicksort 1828 Sorting in Linear Time 2059 Medians and Order Statistics 227III Data Structures Introduction 24910 Elementary Data Structures 25211 Hash Tables 27212 Binary Search Trees 31212 Red-Black Trees 331IV Advanced Design and Analysis Techniques Introduction 36114 Dynamic Programming 36215 Greedy Algorithms 41716 Amortized Analysis 448V Advanced Data StructuresIntroduction 47717 Augmenting Data Structures 48018 B-Trees 49719 Data Structures for Disjoint Sets 520VI Graph Algorithms Introduction 54720 Elementary Graph Algorithms 54921 Minimum Spanning Trees 58522 Single-Source Shortest Paths 60423 All-Pairs Shortest Paths 64624 Maximum Flow 67025 Matchings in Bipartite Graphs 704VII Selected TopicsIntroduction 74526 Parallel Algorithms 74827 Online Algorithms 79128 Matrix Operations 81929 Linear Programming 85030 Polynomials and the FFT 87731 Number-Theoretic Algorithms 90332 String Matching 95733 Machine-Learning Algorithms 100334 NP-Completeness 104235 Approximation Algorithms 1104VIII Appendix: Mathematical BackgroundIntroduction 1139A Summations 1140B Sets, Etc. 1153C Counting and Probability 1178D Matrices 1214Bibliography 1227Index 1251