Introduction to Algorithms

3 /E

Cormen, Thomas H. , Leiserson, Charles E. , Rivest, Ronald L. 저자(글)

MIT · 2009년 09월 01일

책 소개

Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithmsuniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor. The first edition became a widely used text in universities worldwide as well as the standard reference for professionals. The second edition featured new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming. The third edition has been revised and updated throughout. It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, substantial additions to the chapter on recurrence (now called "Divide-and-Conquer"), and an appendix on matrices. It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks. Many new exercises and problems have been added for this edition. As of the third edition, this textbook is published exclusively by the MIT Press.

작가정보

저자(글) Cormen, Thomas H.

Thomas Cormen is Professor of Computer Science at Dartmouth College. Charles Leiserson is Professor of Computer Science and Engineering at MIT. Ronald L. Rivest is Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science at MIT. Clifford Stein is Professor of Industrial Engineering and Operations Research at Columbia University.

저자(글) Leiserson, Charles E.

Charles E. Leiserson is Professor of Computer Science and Engineering at the Massachusetts Institute of Technology.

저자(글) Rivest, Ronald L.

Ronald L. Rivest is Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.

목차

• Prefacep. xiii
  Foundations
  Introductionp. 3
  The Role of Algorithms in Computingp. 5
  Algorithmsp. 5
  Algorithms as a technologyp. 11
  Getting Startedp. 16
  Insertion sortp. 16
  Analyzing algorithmsp. 23
  Designing algorithmsp. 29
  Growth of Functionsp. 43
  Asymptotic notationp. 43
  Standard notations and common functionsp. 53
  Divide-and-Conquerp. 65
  The maximum-subarray problemp. 68
  Strassen's algorithm for matrix multiplicationp. 75
  The substitution method for solving recurrencesp. 83
  The recursion-tree method for solving recurrencesp. 88
  The master method for solving recurrencesp. 93
  Proof of the master theoremp. 97
  Probabilistic Analysis and Randomized Algorithmsp. 114
  The hiring problemp. 114
  Indicator random variablesp. 118
  Randomized algorithmsp. 122
  Probabilistic analysis and further uses of indicator random variablesp. 130
  Sorting and Order Statistics
  Introductionp. 147
  Heapsortp. 151
  Heapsp. 151
  Maintaining the heap propertyp. 154
  Building a heapp. 156
  The heapsort algorithmp. 159
  Priority queuesp. 162
  Quicksortp. 170
  Description of quicksortp. 170
  Performance of quicksortp. 174
  A randomized version of quicksortp. 179
  Analysis of quicksortp. 180
  Sorting in Linear Timep. 191
  Lower bounds for sortingp. 191
  Counting sortp. 194
  Radix sortp. 197
  Bucket sortp. 200
  Medians and Order Statisticsp. 213
  Minimum and maximump. 214
  Selection in expected linear timep. 215
  Selection in worst-case linear timep. 220
  Data Structures
  Introductionp. 229
  Elementary Data Structuresp. 232
  Stacks and queuesp. 232
  Linked listsp. 236
  Implementing pointers and objectsp. 241
  Representing rooted treesp. 246
  Hash Tablesp. 253
  Direct-address tablesp. 254
  Hash tablesp. 256
  Hash functionsp. 262
  Open addressingp. 269
  Perfect hashingp. 277
  Binary Search Treesp. 286
  What is a binary search tree?p. 286
  Querying a binary search treep. 289
  Insertion and deletionp. 294
  Randomly built binary search treesp. 299
  Red-Black Treesp. 308
  Properties of red-black treesp. 308
  Rotationsp. 312
  Insertionp. 315
  Deletionp. 323
  Augmenting Data Structuresp. 339
  Dynamic order statisticsp. 339
  How to augment a data structurep. 345
  Interval treesp. 348
  Advanced Design and Analysis Techniques
  Introductionp. 357
  Dynamic Programmingp. 359
  Rod cuttingp. 360
  Matrix-chain multiplicationp. 370
  Elements of dynamic programmingp. 378
  Longest common subsequencep. 390
  Optimal binary search treesp. 397
  Greedy Algorithmsp. 414
  An activity-selection problemp. 415
  Elements of the greedy strategyp. 423
  Huffman codesp. 428
  Matroids and greedy methodsp. 437
  A task-scheduling problem as a matroidp. 443
  Amortized Analysisp. 451
  Aggregate analysisp. 452
  The accounting methodp. 456
  The potential methodp. 459
  Dynamic tablesp. 463
  Advanced Data Structures
  Introductionp. 481
  B-Treesp. 484
  Definition of B-treesp. 488
  Basic operations on B-treesp. 491
  Deleting a key from a B-treep. 499
  Fibonacci Heapsp. 505
  Structure of Fibonacci heapsp. 507
  Mergeable-heap operationsp. 510
  Decreasing a key and deleting a nodep. 518
  Bounding the maximum degreep. 523
  van Emde Boas Treesp. 531
  Preliminary approachesp. 532
  A recursive structurep. 536
  The van Emde Boas treep. 545
  Data Structures for Disjoint Setsp. 561
  Disjoint-set operationsp. 561
  Linked-list representation of disjoint setsp. 564
  Disjoint-set forestsp. 568
  Analysis of union by rank with path compressionp. 573
  Graph Algorithms
  Introductionp. 587
  Elementary Graph Algorithmsp. 589
  Representations of graphsp. 589
  Breadth-first searchp. 594
  Depth-first searchp. 603
  Topological sortp. 612
  Strongly connected componentsp. 615
  Minimum Spanning Treesp. 624
  Growing a minimum spanning treep. 625
  The algorithms of Kruskal and Primp. 631
  Single-Source Shortest Pathsp. 643
  The Bellman-Ford algorithmp. 651
  Single-source shortest paths in directed acyclic graphsp. 655
  Dijkstra's algorithmp. 658
  Difference constraints and shortest pathsp. 664
  Proofs of shortest-paths propertiesp. 671
  All-Pairs Shortest Pathsp. 684
  Shortest paths and matrix multiplicationp. 686
  The Floyd-Warshall algorithmp. 693
  Johnson's algorithm for sparse graphsp. 700
  Maximum Flowp. 708
  Flow networksp. 709
  The Ford-Fulkerson methodp. 714
  Maximum bipartite matchingp. 732
  Push-relabel algorithmsp. 736
  The relabel-to-front algorithmp. 748
  Selected Topics
  Introductionp. 769
  Multithreaded Algorithmsp. 772
  The basics of dynamic multithreadingp. 774
  Multithreaded matrix multiplicationp. 792
  Multithreaded merge sortp. 797
  Matrix Operationsp. 813
  Solving systems of linear equationsp. 813
  Inverting matricesp. 827
  Symmetric positive-definite matrices and least-squares approximationp. 832
  Linear Programmingp. 843
  Standard and slack formsp. 850
  Formulating problems as linear programsp. 859
  The simplex algorithmp. 864
  Dualityp. 879
  The initial basic feasible solutionp. 886
  Polynomials and the FFTp. 898
  Representing polynomialsp. 900
  The DFT and FFTp. 906
  Efficient FFT implementationsp. 915
  Number-Theoretic Algorithmsp. 926
  Elementary number-theoretic notionsp. 927
  Greatest common divisorp. 933
  Modular arithmeticp. 939
  Solving modular linear equationsp. 946
  The Chinese remainder theoremp. 950
  Powers of an elementp. 954
  The RSA public-key cryptosystemp. 958
  Primality testingp. 965
  Integer factorizationp. 975
  String Matchingp. 985
  The naive string-matching algorithmp. 988
  The Rabin-Karp algorithmp. 990
  String matching with finite automatap. 995
  The Knuth-Morris-Pratt algorithmp. 1002
  Computational Geometryp. 1014
  Line-segment propertiesp. 1015
  Determining whether any pair of segments intersectsp. 1021
  Finding the convex hullp. 1029
  Finding the closest pair of pointsp. 1039
  NP-Completenessp. 1048
  Polynomial timep. 1053
  Polynomial-time verificationp. 1061
  NP-completeness and reducibilityp. 1067
  NP-completeness proofsp. 1078
  NP-complete problemsp. 1086
  Approximation Algorithmsp. 1106
  The vertex-cover problemp. 1108
  The traveling-salesman problemp. 1111
  The set-covering problemp. 1117
  Randomization and linear programmingp. 1123
  The subset-sum problemp. 1128
  Appendix: Mathematical Background
  Introductionp. 1143
  Summationsp. 1145
  Summation formulas and propertiesp. 1145
  Bounding summationsp. 1149
  Sets, Etc.p. 1158
  Setsp. 1158
  Relationsp. 1163
  Functionsp. 1166
  Graphsp. 1168
  Treesp. 1173
  Counting and Probabilityp. 1183
  Countingp. 1183
  Probabilityp. 1189
  Discrete random variablesp. 1196
  The geometric and binomial distributionsp. 1201
  The tails of the binomial distributionp. 1208
  Matricesp. 1217
  Matrices and matrix operationsp. 1217
  Basic matrix propertiesp. 1222
  Bibliographyp. 1231
  Indexp. 1251
  Table of Contents provided by Publisher. All Rights Reserved.

기본정보

ISBN	9780262033848 ( 0262033844 )
발행(출시)일자	2009년 09월 01일
쪽수	1292쪽
크기	208 * 231 * 52 mm / 2200 g
총권수	1권
언어	영어
이 책의 개정정보	새로 출시된 개정판이 있습니다. 개정판보기