Introduction to Algorithms

Autorentext

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Klappentext

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

Zusammenfassung
A comprehensive update of the leading algorithms text, with new material on matchings in bipartite graphs, online algorithms, machine learning, and other topics.

Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. It covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers, with self-contained chapters and algorithms in pseudocode. Since the publication of the first edition, Introduction to Algorithms has become the leading algorithms text in universities worldwide as well as the standard reference for professionals. This fourth edition has been updated throughout.

New for the fourth edition

• New chapters on matchings in bipartite graphs, online algorithms, and machine learning

• New material on topics including solving recurrence equations, hash tables, potential functions, and suffix arrays

• 140 new exercises and 22 new problems

• Reader feedback–informed improvements to old problems

• Clearer, more personal, and gender-neutral writing style

• Color added to improve visual presentation

• Notes, bibliography, and index updated to reflect developments in the field

• Website with new supplementary material
  Warning: Avoid counterfeit copies of Introduction to Algorithms by buying only from reputable retailers. Counterfeit and pirated copies are incomplete and contain errors.

  Inhalt
  Preface xiii
  I Foundations
  Introduction 3
  1 The Role of Algorithms in Computing 5
  2 Getting Started 17
  3 Characterizing Running Times 49
  4 Divide-and-Conquer 76
  5 Probabilistic Analysis and Randomized Algorithms 126
  II Sorting and Order Statistics 
  Introduction 157
  6 Heapsort 161
  7 Quicksort 182
  8 Sorting in Linear Time 205
  9 Medians and Order Statistics 227
  III Data Structures 
  Introduction 249
  10 Elementary Data Structures 252
  11 Hash Tables 272
  12 Binary Search Trees 312
  12 Red-Black Trees 331
  IV Advanced Design and Analysis Techniques 
  Introduction 361
  14 Dynamic Programming 362
  15 Greedy Algorithms 417
  16 Amortized Analysis 448
  V Advanced Data Structures
  Introduction 477
  17 Augmenting Data Structures 480
  18 B-Trees 497
  19 Data Structures for Disjoint Sets 520
  VI Graph Algorithms 
  Introduction 547
  20 Elementary Graph Algorithms 549
  21 Minimum Spanning Trees 585
  22 Single-Source Shortest Paths 604
  23 All-Pairs Shortest Paths 646
  24 Maximum Flow 670
  25 Matchings in Bipartite Graphs 704
  VII Selected Topics
  Introduction 745
  26 Parallel Algorithms 748
  27 Online Algorithms 791
  28 Matrix Operations 819
  29 Linear Programming 850
  30 Polynomials and the FFT 877
  31 Number-Theoretic Algorithms 903
  32 String Matching 957
  33 Machine-Learning Algorithms 1003
  34 NP-Completeness 1042
  35 Approximation Algorithms 1104
  VIII Appendix: Mathematical Background
  Introduction 1139
  A Summations 1140
  B Sets, Etc. 1153
  C Counting and Probability 1178
  D Matrices 1214
  Bibliography 1227
  Index 1251