Transcription
T H O M A S H. C O R M E NC H A R L E S E. L E I S E R S O NR O N A L D L. R I V E S TC L I F F O R D STEININTRODUCTION TOALGORITHMST H I R DE D I T I O N
Introduction to AlgorithmsThird Edition
Thomas H. CormenCharles E. LeisersonRonald L. RivestClifford SteinIntroduction to AlgorithmsThird EditionThe MIT PressCambridge, MassachusettsLondon, England
c 2009 Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means(including photocopying, recording, or information storage and retrieval) without permission in writing from thepublisher.For information about special quantity discounts, please email special sales@mitpress.mit.edu.This book was set in Times Roman and Mathtime Pro 2 by the authors.Printed and bound in the United States of America.Library of Congress Cataloging-in-Publication DataIntroduction to algorithms / Thomas H. Cormen . . . [et al.].—3rd ed.p. cm.Includes bibliographical references and index.ISBN 978-0-262-03384-8 (hardcover : alk. paper)—ISBN 978-0-262-53305-8 (pbk. : alk. paper)1. Computer programming. 2. Computer algorithms. I. Cormen, Thomas H.QA76.6.I5858 2009005.1—dc22200900859310 9 8 7 6 5 4 3 2
ContentsPrefacexiiiI FoundationsIntroduction31The Role of Algorithms in Computing 51.1 Algorithms 51.2 Algorithms as a technology 112Getting Started 162.1 Insertion sort 162.2 Analyzing algorithms 232.3 Designing algorithms 293Growth of Functions 433.1 Asymptotic notation 433.2 Standard notations and common functions4?5?53Divide-and-Conquer 654.1 The maximum-subarray problem 684.2 Strassen’s algorithm for matrix multiplication 754.3 The substitution method for solving recurrences 834.4 The recursion-tree method for solving recurrences 884.5 The master method for solving recurrences 934.6 Proof of the master theorem 97Probabilistic Analysis and Randomized Algorithms 1145.1 The hiring problem 1145.2 Indicator random variables 1185.3 Randomized algorithms 1225.4 Probabilistic analysis and further uses of indicator random variables130
viContentsII Sorting and Order StatisticsIntroduction6789147Heapsort 1516.1 Heaps 1516.2 Maintaining the heap property6.3 Building a heap 1566.4 The heapsort algorithm 1596.5 Priority queues 162154Quicksort 1707.1 Description of quicksort 1707.2 Performance of quicksort 1747.3 A randomized version of quicksort7.4 Analysis of quicksort 180Sorting in Linear Time 1918.1 Lower bounds for sorting8.2 Counting sort 1948.3 Radix sort 1978.4 Bucket sort 200179191Medians and Order Statistics 2139.1 Minimum and maximum 2149.2 Selection in expected linear time 2159.3 Selection in worst-case linear time 220III Data StructuresIntroduction1011?229Elementary Data Structures 23210.1 Stacks and queues 23210.2 Linked lists 23610.3 Implementing pointers and objects10.4 Representing rooted trees 246Hash Tables 25311.1 Direct-address tables 25411.2 Hash tables 25611.3 Hash functions 26211.4 Open addressing 26911.5 Perfect hashing 277241
Contents12?1314viiBinary Search Trees 28612.1 What is a binary search tree? 28612.2 Querying a binary search tree 28912.3 Insertion and deletion 29412.4 Randomly built binary search trees 299Red-Black Trees 30813.1 Properties of red-black trees13.2 Rotations 31213.3 Insertion 31513.4 Deletion 323308Augmenting Data Structures 33914.1 Dynamic order statistics 33914.2 How to augment a data structure14.3 Interval trees 348345IV Advanced Design and Analysis TechniquesIntroduction35715Dynamic Programming 35915.1 Rod cutting 36015.2 Matrix-chain multiplication 37015.3 Elements of dynamic programming 37815.4 Longest common subsequence 39015.5 Optimal binary search trees 39716Greedy Algorithms 41416.1 An activity-selection problem 41516.2 Elements of the greedy strategy 42316.3 Huffman codes 42816.4 Matroids and greedy methods 43716.5 A task-scheduling problem as a matroid?17Amortized Analysis 45117.1 Aggregate analysis 45217.2 The accounting method 45617.3 The potential method 45917.4 Dynamic tables 463443
viiiContentsV Advanced Data StructuresIntroduction18B-Trees 48418.1 Definition of B-trees 48818.2 Basic operations on B-trees 49118.3 Deleting a key from a B-tree 49919Fibonacci Heaps 50519.1 Structure of Fibonacci heaps 50719.2 Mergeable-heap operations 51019.3 Decreasing a key and deleting a node 51819.4 Bounding the maximum degree 52320van Emde Boas Trees 53120.1 Preliminary approaches 53220.2 A recursive structure 53620.3 The van Emde Boas tree 54521Data Structures for Disjoint Sets 56121.1 Disjoint-set operations 56121.2 Linked-list representation of disjoint sets 56421.3 Disjoint-set forests 56821.4 Analysis of union by rank with path compression?VI481Graph AlgorithmsIntroduction58722Elementary Graph Algorithms 58922.1 Representations of graphs 58922.2 Breadth-first search 59422.3 Depth-first search 60322.4 Topological sort 61222.5 Strongly connected components 61523Minimum Spanning Trees 62423.1 Growing a minimum spanning tree 62523.2 The algorithms of Kruskal and Prim 631573
Contents24ixSingle-Source Shortest Paths 64324.1 The Bellman-Ford algorithm 65124.2 Single-source shortest paths in directed acyclic graphs24.3 Dijkstra’s algorithm 65824.4 Difference constraints and shortest paths 66424.5 Proofs of shortest-paths properties 67125All-Pairs Shortest Paths 68425.1 Shortest paths and matrix multiplication 68625.2 The Floyd-Warshall algorithm 69325.3 Johnson’s algorithm for sparse graphs 70026Maximum Flow 70826.1 Flow networks 70926.2 The Ford-Fulkerson method 71426.3 Maximum bipartite matching 73226.4 Push-relabel algorithms 73626.5 The relabel-to-front algorithm 748?655VII Selected TopicsIntroduction76927Multithreaded Algorithms 77227.1 The basics of dynamic multithreading 77427.2 Multithreaded matrix multiplication 79227.3 Multithreaded merge sort 79728Matrix Operations 81328.1 Solving systems of linear equations 81328.2 Inverting matrices 82728.3 Symmetric positive-definite matrices and least-squares approximation83229Linear Programming 84329.1 Standard and slack forms 85029.2 Formulating problems as linear programs29.3 The simplex algorithm 86429.4 Duality 87929.5 The initial basic feasible solution 886859
xContents30Polynomials and the FFT 89830.1 Representing polynomials 90030.2 The DFT and FFT 90630.3 Efficient FFT implementations 91531Number-Theoretic Algorithms 92631.1 Elementary number-theoretic notions 92731.2 Greatest common divisor 93331.3 Modular arithmetic 93931.4 Solving modular linear equations 94631.5 The Chinese remainder theorem 95031.6 Powers of an element 95431.7 The RSA public-key cryptosystem 95831.8 Primality testing 96531.9 Integer factorization 975?32?33String Matching 98532.1 The naive string-matching algorithm 98832.2 The Rabin-Karp algorithm 99032.3 String matching with finite automata 99532.4 The Knuth-Morris-Pratt algorithm 1002Computational Geometry 101433.1 Line-segment properties 101533.2 Determining whether any pair of segments intersects33.3 Finding the convex hull 102933.4 Finding the closest pair of points 103934NP-Completeness 104834.1 Polynomial time 105334.2 Polynomial-time verification 106134.3 NP-completeness and reducibility 106734.4 NP-completeness proofs 107834.5 NP-complete problems 108635Approximation Algorithms 110635.1 The vertex-cover problem 110835.2 The traveling-salesman problem 111135.3 The set-covering problem 111735.4 Randomization and linear programming35.5 The subset-sum problem 112811231021
ContentsxiVIII Appendix: Mathematical BackgroundIntroductionA1143Summations 1145A.1 Summation formulas and propertiesA.2 Bounding summations 11491145BSets, Etc. 1158B.1 Sets 1158B.2 Relations 1163B.3 Functions 1166B.4 Graphs 1168B.5 Trees 1173CCounting and Probability 1183C.1 Counting 1183C.2 Probability 1189C.3 Discrete random variables 1196C.4 The geometric and binomial distributions 1201C.5 The tails of the binomial distribution 1208?DMatrices 1217D.1 Matrices and matrix operationsD.2 Basic matrix properties 1222BibliographyIndex125112311217
PrefaceBefore there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing.This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerabledepth, yet makes their design and analysis accessible to all levels of readers. Wehave tried to keep explanations elementary without sacrificing depth of coverageor mathematical rigor.Each chapter presents an algorithm, a design technique, an application area, or arelated topic. Algorithms are described in English and in a pseudocode designed tobe readable by anyone who has done a little programming. The book contains 244figures—many with multiple parts—illustrating how the algorithms work. Sincewe emphasize efficiency as a design criterion, we include careful analyses of therunning times of all our algorithms.The text is intended primarily for use in undergraduate or graduate courses inalgorithms or data structures. Because it discusses engineering issues in algorithmdesign, as well as mathematical aspects, it is equally well suited for self-study bytechnical professionals.In this, the third edition, we have once again updated the entire book. Thechanges cover a broad spectrum, including new chapters, revised pseudocode, anda more active writing style.To the teacherWe have designed this book to be both versatile and complete. You should find ituseful for a variety of courses, from an undergraduate course in data structures upthrough a graduate course in algorithms. Because we have provided considerablymore material than can fit in a typical one-term course, you can consider this bookto be a “buffet” or “smorgasbord” from which you can pick and choose the materialthat best supports the course you wish to teach.
xivPrefaceYou should find it easy to organize your course around just the chapters youneed. We have made chapters relatively self-contained, so that you need not worryabout an unexpected and unnecessary dependence of one chapter on another. Eachchapter presents the easier material first and the more difficult material later, withsection boundaries marking natural stopping points. In an undergraduate course,you might use only the earlier sections from a chapter; in a graduate course, youmight cover the entire chapter.We have included 957 exercises and 158 problems. Each section ends with exercises, and each chapter ends with problems. The exercises are generally short questions that test basic mastery of the material. Some are simple self-check thoughtexercises, whereas others are more substantial and are suitable as assigned homework. The problems are more elaborate case studies that often introduce new material; they often consist of several questions that lead the student through the stepsrequired to arrive at a solution.Departing from our practice in previous editions of this book, we have madepublicly available solutions to some, but by no means all, of the problems and exercises. Our Web site, http://mitpress.mit.edu/algorithms/, links to these solutions.You will want to check this site to make sure that it does not contain the solution toan exercise or problem that you plan to assign. We expect the set of solutions thatwe post to grow slowly over time, so you will need to check it each time you teachthe course.We have starred (?) the sections and exercises that are more suitable for graduatestudents than for undergraduates. A starred section is not necessarily more difficult than an unstarred one, but it may require an understanding of more advancedmathematics. Likewise, starred exercises may require an advanced background ormore than average creativity.To the studentWe hope that this textbook provides you with an enjoyable introduction to thefield of algorithms. We have attempted to make every algorithm accessible andinteresting. To help you when you encounter unfamiliar or difficult algorithms, wedescribe each one in a step-by-step manner. We also provide careful explanationsof the mathematics needed to understand the analysis of the algorithms. If youalready have some familiarity with a topic, you will find the chapters organized sothat you can skim introductory sections and proceed quickly to the more advancedmaterial.This is a large book, and your class will probably cover only a portion of itsmaterial. We have tried, however, to make this a book that will be useful to younow as a course textbook and also later in your career as a mathematical deskreference or an engineering handbook.
PrefacexvWhat are the prerequisites for reading this book? You should have some programming experience. In particular, you should understand recursive procedures and simple data structures such as arrays andlinked lists. You should have some facility with mathematical proofs, and especially proofsby mathematical induction. A few portions of the book rely on some knowledgeof elementary calculus. Beyond that, Parts I and VIII of this book teach you allthe mathematical techniques you will need.We have heard, loud and clear, the call to supply solutions to problems andexercises. Our Web site, http://mitpress.mit.edu/algorithms/, links to solutions fora few of the problems and exercises. Feel free to check your solutions against ours.We ask, however, that you do not send your solutions to us.To the professionalThe wide range of topics in this book makes it an excellent handbook on algorithms. Because each chapter is relatively self-contained, you can focus in on thetopics that most interest you.Most of the algorithms we discuss have great practical utility. We thereforeaddress implementation concerns and other engineering issues. We often providepractical alternatives to the few algorithms that are primarily of theoretical interest.If you wish to implement any of the algorithms, you should find the translation of our pseudocode into your favori
This book provides a comprehensive introduction to the modern study of com-puter algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor. Each chapter presents an algorithm, a design technique .
