《算法导论》- Introduction to Algorithms (Second Edition)

PDF_TYPE:mixed PAGE_COUNT:1203 =MARKDOWN=

Introduction to Algorithms

Second Edition

This page intentionally left blank

Thomas H. Cormen

Charles E. Leiserson

Ronald L. Rivest

Clifford Stein

Introduction to Algorithms

Second Edition

The MIT Press Cambridge, Massachusetts London, England

McGraw-Hill Book Company Boston Burr Ridge, IL Dubuque, IA Madison, WI New York San Francisco St. Louis Montr´eal Toronto

This book is one of a series of texts written by faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology. It was edited and produced by The MIT Press under a joint production-distribution agreement with the McGraw-Hill Book Company. Ordering Information: North America Text orders should be addressed to the McGraw-Hill Book Company. All other orders should be addressed to The MIT Press. Outside North America All orders should be addressed to The MIT Press or its local distributor. Third printing, 2002 ©c 2001 by The Massachusetts Institute of Technology First edition 1990 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 the publisher. This book was printed and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Introduction to algorithms / Thomas H. Cormen …[etal.].—2nded.

p. cm. Includes bibliographical references and index. ISBN 0-262-03293-7 (hc. : alk. paper, MIT Press).—ISBN 0-07-013151-1 (McGraw-Hill)

1. Computer programming. 2. Computer algorithms. I. Title: Algorithms. II. Cormen, Thomas H.

QA76.6 I5858 2001

005.1—dc21 2001031277

Contents

Preface xiii

I Foundations

Introduction 3 1 The Role of Algorithms in Computing 1.1 Algorithms 5 1.2 Algorithms as a technology 10 2 Getting Started 15 2.1 Insertion sort 15 2.2 Analyzing algorithms 21 2.3 Designing algorithms 27 3 Growth of Functions 41 3.1 Asymptotic notation 41 3.2 Standard notations and common functions 4 Recurrences 62 4.1 The substitution method 63 4.2 The recursion-tree method 67 4.3 The master method 73 4.4Proofofthemastertheorem 76 5 Probabilistic Analysis and Randomized Algorithms 5.1 The hiring problem 91 5.2 Indicator random variables 94 5.3 Randomized algorithms 99 5.4 Probabilistic analysis and further uses of indicator random variables

5

51

91

106

vi Contents

II Sorting and Order Statistics

Introduction 123 6Heapsort 127 6.1 Heaps 127 6.2 Maintaining the heap property 130 6.3 Building a heap 132 6.4 The heapsort algorithm 135 6.5 Priority queues 138 7 Quicksort 145 7.1 Description of quicksort 145 7.2 Performance of quicksort 149 7.3 A randomized version of quicksort 7.4 Analysis of quicksort 155 8 Sorting in Linear Time 165 8.1 Lower bounds for sorting 165 8.2 Counting sort 168 8.3 Radix sort 170 8.4 Bucket sort 174 9 Medians and Order Statistics 183 9.1 Minimum and maximum 184 9.2 Selection in expected linear time 185 9.3 Selection in worst-case linear time

153

189

III Data Structures

Introduction 197 10 Elementary Data Structures 200 10.1 Stacks and queues 200 10.2 Linked lists 204 10.3 Implementing pointers and objects 10.4 Representing rooted trees 214 11 Hash Tables 221 11.1 Direct-address tables 222 11.2 Hash tables 224 11.3 Hash functions 229 11.4 Open addressing 237 11.5 Perfect hashing 245

209

Contents vii

12 Binary Search Trees		253
12.1	What is a binary search tree?		253
12.2Queryingabinarysearchtree			256
12.3	Insertion and deletion		261
12.4Randomlybuiltbinarysearchtrees				265
13 Red-Black Trees		273
13.1	Properties of red-black trees		273
13.2	Rotations	277
13.3	Insertion	280
13.4	Deletion	288
14 Augmenting Data Structures			302
14.1	Dynamic order statistics		302
14.2	How to augment a data structure			308
14.3	Interval trees	311

IV Advanced Design and Analysis Techniques

Introduction 321 15 Dynamic Programming 323 15.1 Assembly-line scheduling 324 15.2 Matrix-chain multiplication 331 15.3 Elements of dynamic programming 15.4 Longest common subsequence 350 15.5 Optimal binary search trees 356 16 Greedy Algorithms 370 16.1 An activity-selection problem 371 16.2 Elements of the greedy strategy 379 16.3 Huffman codes 385 16.4 Theoretical foundations for greedy methods 16.5 A task-scheduling problem 399 17 Amortized Analysis 405 17.1 Aggregate analysis 406 17.2 The accounting method 410 17.3 The potential method 17.4 Dynamic tables 416

339

393

412

viii Contents

V Advanced Data Structures

Introduction 431 18 B-Trees 434 18.1 Definition of B-trees 18.2 Basic operations on B-trees 441 18.3 Deleting a key from a B-tree 449 19 Binomial Heaps 455 19.1 Binomial trees and binomial heaps 457 19.2 Operations on binomial heaps 461 20 Fibonacci Heaps 476 20.1 Structure of Fibonacci heaps 477 20.2 Mergeable-heap operations 479 20.3 Decreasing a key and deleting a node 489 20.4 Bounding the maximum degree 493 21 Data Structures for Disjoint Sets 498 21.1 Disjoint-set operations 498 21.2 Linked-list representation of disjoint sets 501 21.3 Disjoint-set forests 21.4 Analysis of union by rank with path compression

438

505 509

VI Graph Algorithms

Introduction 525

22 Elementary Graph Algorithms 527 22.1 Representations of graphs 527 22.2 Breadth-first search 531 22.3 Depth-first search 540 22.4 Topological sort 549 22.5 Strongly connected components 552 23 Minimum Spanning Trees 561 23.1 Growing a minimum spanning tree 562 23.2 The algorithms of Kruskal and Prim 567 24 Single-Source Shortest Paths 580 24.1 The Bellman-Ford algorithm 588 24.2 Single-source shortest paths in directed acyclic graphs 24.3 Dijkstra’s algorithm 595 24.4 Difference constraints and shortest paths 601 24.5 Proofs of shortest-paths properties 607

592

Contents ix

25 All-Pairs Shortest Paths 620

25.1 Shortest paths and matrix multiplication 622

25.1	Shortest paths and matrix multiplication			622
25.2	The Floyd-Warshall algorithm		629
25.3	Johnson’s algorithm for sparse graphs			636
26 Maximum Flow		643
26.1	Flow networks	644
26.2	The Ford-Fulkerson method		651
26.3	Maximum bipartite matching		664
26.4	Push-relabel algorithms		669
26.5	The relabel-to-front algorithm		681

VII Selected Topics

Introduction 701

27 Sorting Networks 704

27.1 Comparison networks 704 27.2 The zero-one principle 709 27.3 A bitonic sorting network 712 27.4 A merging network 716 27.5 A sorting network 719

28 Matrix Operations 725

28.1 Properties of matrices 725 28.2 Strassen’s algorithm for matrix multiplication 735 28.3 Solving systems of linear equations 742 28.4 Inverting matrices 755 28.5 Symmetric positive-definite matrices and least-squares approximation 760

29 Linear Programming 770

29.1 Standard and slack forms 777 29.2 Formulating problems as linear programs 785 29.3 The simplex algorithm 790 29.4 Duality 804 29.5 The initial basic feasible solution 811

30 Polynomials and the FFT 822

30.1 Representation of polynomials 824 30.2 The DFT and FFT 830 30.3 Efficient FFT implementations 839

x Contents

31 Number-Theoretic Algorithms 849 31.1 Elementary number-theoretic notions 850 31.2 Greatest common divisor 856 31.3 Modular arithmetic 862 31.4 Solving modular linear equations 869 31.5 The Chinese remainder theorem 873 31.6 Powers of an element 876 31.7 The RSA public-key cryptosystem 881 31.8 Primality testing 887 31.9 Integer factorization 896 32 String Matching 32.1 The naive string-matching algorithm 909 32.2 The Rabin-Karp algorithm 911 32.3 String matching with finite automata 916 32.4 The Knuth-Morris-Pratt algorithm 923 33 Computational Geometry 933 33.1 Line-segment properties 934 33.2 Determining whether any pair of segments intersects 33.3 Finding the convex hull 947 33.4 Finding the closest pair of points 957 34 NP-Completeness 34.1 Polynomial time 971 34.2 Polynomial-time verification 979 34.3 NP-completeness and reducibility 984 34.4 NP-completeness proofs 995 34.5 NP-complete problems 1003 35 Approximation Algorithms 1022 35.1 The vertex-cover problem 1024 35.2 The traveling-salesman problem 1027 35.3 The set-covering problem 1033 35.4 Randomization and linear programming 1039 35.5 The subset-sum problem 1043

906

940

966

VIII Appendix: Mathematical Background

Introduction 1057

A Summations 1058

A.1 Summation formulas and properties 1058 A.2 Bounding summations 1062

Contents xi

B Sets, Etc. 1070

B.1 Sets 1070 B.2 Relations 1075 B.3 Functions 1077 B.4 Graphs 1080 B.5 Trees 1085

C Counting and Probability 1094

C.1 Counting 1094 C.2 Probability 1100 C.3 Discrete random variables 1106 C.4 The geometric and binomial distributions 1112 C.5 The tails of the binomial distribution 1118

Bibliography 1127

Index 1145

This page intentionally left blank

Preface

This book provides a comprehensive introduction to the modern study of computer 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, an application area, or a related topic. Algorithms are described in English and in a “pseudocode” designed to be readable by anyone who has done a little programming. The book contains over 230 figures illustrating how the algorithms work. Since we emphasize efficiency as a design criterion, we include careful analyses of the running times of all our algorithms. The text is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Because it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals. In this, the second edition, we have updated the entire book. The changes range from the addition of new chapters to the rewriting of individual sentences.

To the teacher

This book is designed to be both versatile and complete. You will find it useful for a variety of courses, from an undergraduate course in data structures up through a graduate course in algorithms. Because we have provided considerably more material than can fit in a typical one-term course, you should think of the book as a “buffet” or “smorgasbord” from which you can pick and choose the material that best supports the course you wish to teach. You should find it easy to organize your course around just the chapters you need. We have made chapters relatively self-contained, so that you need not worry about an unexpected and unnecessary dependence of one chapter on another. Each chapter presents the easier material first and the more difficult material later, with

xiv Preface

section boundaries marking natural stopping points. In an undergraduate course, you might use only the earlier sections from a chapter; in a graduate course, you might cover the entire chapter. We have included over 920 exercises and over 140 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 thought exercises, whereas others are more substantial and are suitable as assigned homework. The problems are more elaborate case studies that often introduce new material; they typically consist of several questions that lead the student through the steps required to arrive at a solution. We have starred ( ) the sections and exercises that are more suitable for graduate students than for undergraduates. A starred section is not necessarily more difficult than an unstarred one, but it may require an understanding of more advanced mathematics. Likewise, starred exercises may require an advanced background or more than average creativity.

To the student

We hope that this textbook provides you with an enjoyable introduction to the field of algorithms. We have attempted to make every algorithm accessible and interesting. To help you when you encounter unfamiliar or difficult algorithms, we describe each one in a step-by-step manner. We also provide careful explanations of the mathematics needed to understand the analysis of the algorithms. If you already have some familiarity with a topic, you will find the chapters organized so that you can skim introductory sections and proceed quickly to the more advanced material. This is a large book, and your class will probably cover only a portion of its material. We have tried, however, to make this a book that will be useful to you now as a course textbook and also later in your career as a mathematical desk reference or an engineering handbook. What 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 and linked lists. •You should have some facility with proofs by mathematical induction. A few portions of the book rely on some knowledge of elementary calculus. Beyond that, Parts I and VIII of this book teach you all the mathematical techniques you will need.

Preface xv

To the professional

The 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 the topics that most interest you. Most of the algorithms we discuss have great practical utility. We therefore address implementation concerns and other engineering issues. We often provide practical alternatives to the few algorithms that are primarily of theoretical interest. If you wish to implement any of the algorithms, you will find the translation of our pseudocode into your favorite programming language a fairly straightforward task. The pseudocode is designed to present each algorithm clearly and succinctly. Consequently, we do not address error-handling and other software-engineering issues that require specific assumptions about your programming environment. We attempt to present each algorithm simply and directly without allowing the idiosyn- crasies of a particular programming language to obscure its essence.

To our colleagues

We have supplied an extensive bibliography and pointers to the current literature. Each chapter ends with a set of “chapter notes” that give historical details and references. The chapter notes do not provide a complete reference to the whole field of algorithms, however. Though it may be hard to believe for a book of this size, many interesting algorithms could not be included due to lack of space. Despite myriad requests from students for solutions to problems and exercises, we have chosen as a matter of policy not to supply references for problems and exercises, to remove the temptation for students to look up a solution rather than to find it themselves.

Changes for the second edition

What has changed between the first and second editions of this book? Depending on how you look at it, either not much or quite a bit. A quick look at the table of contents shows that most of the first-edition chapters and sections appear in the second edition. We removed two chapters and a handful of sections, but we have added three new chapters and four new sections apart from these new chapters. If you were to judge the scope of the changes by the table of contents, you would likely conclude that the changes were modest. The changes go far beyond what shows up in the table of contents, however. In no particular order, here is a summary of the most significant changes for the second edition:

xvi Preface

•Cliff Stein was added as a coauthor.

•Errors have been corrected. How many errors? Let’s just say several.

•There are three new chapters:

•Chapter 1 discusses the role of algorithms in computing. •Chapter 5 covers probabilistic analysis and randomized algorithms. As in the first edition, these topics appear throughout the book. •Chapter 29 is devoted to linear programming.

•Within chapters that were carried over from the first edition, there are new sections on the following topics:

•perfect hashing (Section 11.5), •two applications of dynamic programming (Sections 15.1 and 15.5), and •approximation algorithms that use randomization and linear programming (Section 35.4).

•To allow more algorithms to appear earlier in the book, three of the chapters on mathematical background have been moved from Part I to the Appendix, which is Part VIII. •There are over 40 new problems and over 185 new exercises.

•We have made explicit the use of loop invariants for proving correctness. Our first loop invariant appears in Chapter 2, and we use them a couple of dozen times throughout the book. •Many of the probabilistic analyses have been rewritten. In particular, we use in a dozen places the technique of “indicator random variables,” which simplify probabilistic analyses, especially when random variables are dependent. •We have expanded and updated the chapter notes and bibliography. The bibliography has grown by over 50%, and we have mentioned many new algorithmic results that have appeared subsequent to the printing of the first edition.

We have also made the following changes:

•The chapter on solving recurrences no longer contains the iteration method. Instead, in Section 4.2, we have “promoted” recursion trees to constitute a method in their own right. We have found that drawing out recursion trees is less error-prone than iterating recurrences. We do point out, however, that recursion trees are best used as a way to generate guesses that are then verified via the substitution method.

Preface xvii

•The partitioning method used for quicksort (Section 7.1) and the expected linear-time order-statistic algorithm (Section 9.2) is different. We now use the method developed by Lomuto, which, along with indicator random variables, allows for a somewhat simpler analysis. The method from the first edition, due to Hoare, appears as a problem in Chapter 7. •We have modified the discussion of universal hashing in Section 11.3.3 so that it integrates into the presentation of perfect hashing. •There is a much simpler analysis of the height of a randomly built binary search tree in Section 12.4. •The discussions on the elements of dynamic programming (Section 15.3) and the elements of greedy algorithms (Section 16.2) are significantly expanded. The exploration of the activity-selection problem, which starts off the greedy-algorithms chapter, helps to clarify the relationship between dynamic programming and greedy algorithms. •We have replaced the proof of the running time of the disjoint-set-union data structure in Section 21.4 with a proof that uses the potential method to derive a tight bound. •The proof of correctness of the algorithm for strongly connected components in Section 22.5 is simpler, clearer, and more direct. •Chapter 24, on single-source shortest paths, has been reorganized to move proofs of the essential properties to their own section. The new organization allows us to focus earlier on algorithms. •Section 34.5 contains an expanded overview of NP-completeness as well as new NP-completeness proofs for the hamiltonian-cycle and subset-sum problems.

Finally, virtually every section has been edited to correct, simplify, and clarify explanations and proofs.

Web site

Another change from the first edition is that this book now has its own web site: http://mitpress.mit.edu/algorithms/. You can use the web site to report errors, obtain a list of known errors, or make suggestions; we would like to hear from you. We particularly welcome ideas for new exercises and problems, but please include solutions. We regret that we cannot personally respond to all comments.

xviii Preface

Acknowledgments for the first edition

Many friends and colleagues have contributed greatly to the quality of this book. We thank all of you for your help and constructive criticisms. MIT’s Laboratory for Computer Science has provided an ideal working environment. Our colleagues in the laboratory’s Theory of Computation Group have been particularly supportive and tolerant of our incessant requests for critical appraisal of chapters. We specifically thank Baruch Awerbuch, Shafi Goldwasser, Leo Guibas, Tom Leighton, Albert Meyer, David Shmoys, and Eva Tardos. Thanks to William ´ Ang, Sally Bemus, Ray Hirschfeld, and Mark Reinhold for keeping our machines (DEC Microvaxes, Apple Macintoshes, and Sun Sparcstations) running and for re- compiling TEX whenever we exceeded a compile-time limit. Thinking Machines Corporation provided partial support for Charles Leiserson to work on this book during a leave of absence from MIT. Many colleagues have used drafts of this text in courses at other schools. They have suggested numerous corrections and revisions. We particularly wish to thank Richard Beigel, Andrew Goldberg, Joan Lucas, Mark Overmars, Alan Sherman, and Diane Souvaine. Many teaching assistants in our courses have made significant contributions to the development of this material. We especially thank Alan Baratz, Bonnie Berger, Aditi Dhagat, Burt Kaliski, Arthur Lent, Andrew Moulton, Marios Papaefthymiou, Cindy Phillips, Mark Reinhold, Phil Rogaway, Flavio Rose, Arie Rudich, Alan Sherman, Cliff Stein, Susmita Sur, Gregory Troxel, and Margaret Tuttle. Additional valuable technical assistance was provided by many individuals. Denise Sergent spent many hours in the MIT libraries researching bibliographic references. Maria Sensale, the librarian of our reading room, was always cheerful and helpful. Access to Albert Meyer’s personal library saved many hours of library time in preparing the chapter notes. Shlomo Kipnis, Bill Niehaus, and David Wilson proofread old exercises, developed new ones, and wrote notes on their solutions. Marios Papaefthymiou and Gregory Troxel contributed to the indexing. Over the years, our secretaries Inna Radzihovsky, Denise Sergent, Gayle Sherman, and especially Be Blackburn provided endless support in this project, for which we thank them. Many errors in the early drafts were reported by students. We particularly thank Bobby Blumofe, Bonnie Eisenberg, Raymond Johnson, John Keen, Richard Lethin, Mark Lillibridge, John Pezaris, Steve Ponzio, and Margaret Tuttle for their careful readings. Colleagues have also provided critical reviews of specific chapters, or information on specific algorithms, for which we are grateful. We especially thank Bill Aiello, Alok Aggarwal, Eric Bach, Vaˇsek Chv´atal, Richard Cole, Johan Hastad, Alex Ishii, David Johnson, Joe Kilian, Dina Kravets, Bruce Maggs, Jim Orlin, James Park, Thane Plambeck, Hershel Safer, Jeff Shallit, Cliff Stein, Gil Strang,

Preface xix

Bob Tarjan, and Paul Wang. Several of our colleagues also graciously supplied us with problems; we particularly thank Andrew Goldberg, Danny Sleator, and Umesh Vazirani. It has been a pleasure working with The MIT Press and McGraw-Hill in the development of this text. We especially thank Frank Satlow, Terry Ehling, Larry Cohen, and Lorrie Lejeune of The MIT Press and David Shapiro of McGraw-Hill for their encouragement, support, and patience. We are particularly grateful to Larry Cohen for his outstanding copyediting.

Acknowledgments for the second edition

When we asked Julie Sussman, P.P.A., to serve as a technical copyeditor for the second edition, we did not know what a good deal we were getting. In addition to copyediting the technical content, Julie enthusiastically edited our prose. It is humbling to think of how many errors Julie found in our earlier drafts, though considering how many errors she found in the first edition (after it was printed, unfortunately), it is not surprising. Moreover, Julie sacrificed her own schedule to accommodate ours—she even brought chapters with her on a trip to the Virgin Islands! Julie, we cannot thank you enough for the amazing job you did. The work for the second edition was done while the authors were members of the Department of Computer Science at Dartmouth College and the Laboratory for Computer Science at MIT. Both were stimulating environments in which to work, and we thank our colleagues for their support. Friends and colleagues all over the world have provided suggestions and opin- ions that guided our writing. Many thanks to Sanjeev Arora, Javed Aslam, Guy Blelloch, Avrim Blum, Scot Drysdale, Hany Farid, Hal Gabow, Andrew Goldberg, David Johnson, Yanlin Liu, Nicolas Schabanel, Alexander Schrijver, Sasha Shen, David Shmoys, Dan Spielman, Gerald Jay Sussman, Bob Tarjan, Mikkel Thorup, and Vijay Vazirani. Many teachers and colleagues have taught us a great deal about algorithms. We particularly acknowledge our teachers Jon L. Bentley, Bob Floyd, Don Knuth, Harold Kuhn, H. T. Kung, Richard Lipton, Arnold Ross, Larry Snyder, Michael I. Shamos, David Shmoys, Ken Steiglitz, Tom Szymanski, Eva Tardos, Bob Tarjan, ´ and Jeffrey Ullman. We acknowledge the work of the many teaching assistants for the algorithms courses at MIT and Dartmouth, including Joseph Adler, Craig Barrack, Bobby Blumofe, Roberto De Prisco, Matteo Frigo, Igal Galperin, David Gupta, Raj D. Iyer, Nabil Kahale, Sarfraz Khurshid, Stavros Kolliopoulos, Alain Leblanc, Yuan Ma, Maria Minkoff, Dimitris Mitsouras, Alin Popescu, Harald Prokop, Sudipta Sengupta, Donna Slonim, Joshua A. Tauber, Sivan Toledo, Elisheva Werner-Reiss, Lea Wittie, Qiang Wu, and Michael Zhang.

xx Preface

Computer support was provided by William Ang, Scott Blomquist, and Greg Shomo at MIT and by Wayne Cripps, John Konkle, and Tim Tregubov at Dartmouth. Thanks also to Be Blackburn, Don Dailey, Leigh Deacon, Irene Sebeda, and Cheryl Patton Wu at MIT and to Phyllis Bellmore, Kelly Clark, Delia Mauceli, Sammie Travis, Deb Whiting, and Beth Young at Dartmouth for administrative support. Michael Fromberger, Brian Campbell, Amanda Eubanks, Sung Hoon Kim, and Neha Narula also provided timely support at Dartmouth. Many people were kind enough to report errors in the first edition. We thank the following people, each of whom was the first to report an error from the first edition: Len Adleman, Selim Akl, Richard Anderson, Juan Andrade-Cetto, Gregory Bachelis, David Barrington, Paul Beame, Richard Beigel, Margrit Betke, Alex Blakemore, Bobby Blumofe, Alexander Brown, Xavier Cazin, Jack Chan, Richard Chang, Chienhua Chen, Ien Cheng, Hoon Choi, Drue Coles, Christian Collberg, George Collins, Eric Conrad, Peter Csaszar, Paul Dietz, Martin Dietzfelbinger, Scot Drysdale, Patricia Ealy, Yaakov Eisenberg, Michael Ernst, Michael For- mann, Nedim Fresko, Hal Gabow, Marek Galecki, Igal Galperin, Luisa Gargano, John Gately, Rosario Genario, Mihaly Gereb, Ronald Greenberg, Jerry Gross- man, Stephen Guattery, Alexander Hartemik, Anthony Hill, Thomas Hofmeister, Mathew Hostetter, Yih-Chun Hu, Dick Johnsonbaugh, Marcin Jurdzinki, Nabil Kahale, Fumiaki Kamiya, Anand Kanagala, Mark Kantrowitz, Scott Karlin, Dean Kelley, Sanjay Khanna, Haluk Konuk, Dina Kravets, Jon Kroger, Bradley Kusz- maul, Tim Lambert, Hang Lau, Thomas Lengauer, George Madrid, Bruce Maggs, Victor Miller, Joseph Muskat, Tung Nguyen, Michael Orlov, James Park, Seongbin Park, Ioannis Paschalidis, Boaz Patt-Shamir, Leonid Peshkin, Patricio Poblete, Ira Pohl, Stephen Ponzio, Kjell Post, Todd Poynor, Colin Prepscius, Sholom Rosen, Dale Russell, Hershel Safer, Karen Seidel, Joel Seiferas, Erik Seligman, Stanley Selkow, Jeffrey Shallit, Greg Shannon, Micha Sharir, Sasha Shen, Norman Shul- man, Andrew Singer, Daniel Sleator, Bob Sloan, Michael Sofka, Volker Strumpen, Lon Sunshine, Julie Sussman, Asterio Tanaka, Clark Thomborson, Nils Thomme- sen, Homer Tilton, Martin Tompa, Andrei Toom, Felzer Torsten, Hirendu Vaishnav,

M. Veldhorst, Luca Venuti, Jian Wang, Michael Wellman, Gerry Wiener, Ronald Williams, David Wolfe, Jeff Wong, Richard Woundy, Neal Young, Huaiyuan Yu, Tian Yuxing, Joe Zachary, Steve Zhang, Florian Zschoke, and Uri Zwick. Many of our colleagues provided thoughtful reviews or filled out a long survey. We thank reviewers Nancy Amato, Jim Aspnes, Kevin Compton, William Evans, Peter Gacs, Michael Goldwasser, Andrzej Proskurowski, Vijaya Ramachan- dran, and John Reif. We also thank the following people for sending back the survey: James Abello, Josh Benaloh, Bryan Beresford-Smith, Kenneth Blaha, Hans Bodlaender, Richard Borie, Ted Brown, Domenico Cantone, M. Chen, Robert Cimikowski, William Clocksin, Paul Cull, Rick Decker, Matthew Dick- erson, Robert Douglas, Margaret Fleck, Michael Goodrich, Susanne Hambrusch,

Preface xxi

Dean Hendrix, Richard Johnsonbaugh, Kyriakos Kalorkoti, Srinivas Kankanahalli, Hikyoo Koh, Steven Lindell, Errol Lloyd, Andy Lopez, Dian Rae Lopez, George Lucker, David Maier, Charles Martel, Xiannong Meng, David Mount, Alberto Poli- criti, Andrzej Proskurowski, Kirk Pruhs, Yves Robert, Guna Seetharaman, Stanley Selkow, Robert Sloan, Charles Steele, Gerard Tel, Murali Varanasi, Bernd Walter, and Alden Wright. We wish we could have carried out all your suggestions. The only problem is that if we had, the second edition would have been about 3000 pages long! The second edition was produced in LATEX2ε. Michael Downes converted the L A TEX macros from “classic” LATEXtoLATEX2ε, and he converted the text files to use these new macros. David Jones also provided LATEX2ε support. Figures for the second edition were produced by the authors using MacDraw Pro. As in the first edition, the index was compiled using Windex, a C program written by the authors, and the bibliography was prepared using BIBTEX. Ayorkor Mills-Tettey and Rob Leathern helped convert the figures to MacDraw Pro, and Ayorkor also checked our bibliography. As it was in the first edition, working with The MIT Press and McGraw-Hill has been a delight. Our editors, Bob Prior of The MIT Press and Betsy Jones of McGraw-Hill, put up with our antics and kept us going with carrots and sticks. Finally, we thank our wives—Nicole Cormen, Gail Rivest, and Rebecca Ivry— our children—Ricky, William, and Debby Leiserson; Alex and Christopher Rivest; Noah, Stein—and

and Molly,	and Benjamin	our parents—Renee	and	Perry
Cormen, Jean and Mark Leiserson, Shirley and Lloyd Rivest, and Irene and Ira
Stein—for their love and support during the writing of this book.			The patience
and encouragement of our families made this project possible. dedicate this book to them.			We affectionately
THOMAS H. CORMEN		Hanover, New Hampshire
CHARLES E. LEISERSON		Cambridge, Massachusetts
RONALD L. RIVEST		Cambridge, Massachusetts
CLIFFORD STEIN		Hanover, New Hampshire

May 2001

This page intentionally left blank

Introduction to Algorithms

Second Edition

I Foundations

Introduction

This part will get you started in thinking about designing and analyzing algorithms. It is intended to be a gentle introduction to how we specify algorithms, some of the design strategies we will use throughout this book, and many of the fundamental ideas used in algorithm analysis. Later parts of this book will build upon this base. Chapter 1 is an overview of algorithms and their place in modern computing systems. This chapter defines what an algorithm is and lists some examples. It also makes a case that algorithms are a technology, just as are fast hardware, graphical user interfaces, object-oriented systems, and networks. In Chapter 2, we see our first algorithms, which solve the problem of sorting a sequence of n numbers. They are written in a pseudocode which, although not directly translatable to any conventional programming language, conveys the structure of the algorithm clearly enough that a competent programmer can implement it in the language of his choice. The sorting algorithms we examine are insertion sort, which uses an incremental approach, and merge sort, which uses a recursive technique known as “divide and conquer.” Although the time each requires increases with the value of n, the rate of increase differs between the two algorithms. We determine these running times in Chapter 2, and we develop a useful notation to express them. Chapter 3 precisely defines this notation, which we call asymptotic notation. It starts by defining several asymptotic notations, which we use for bounding algorithm running times from above and/or below. The rest of Chapter 3 is primarily a presentation of mathematical notation. Its purpose is more to ensure that your use of notation matches that in this book than to teach you new mathematical concepts.

Part I Foundations

Chapter 4 delves further into the divide-and-conquer method introduced in Chapter 2. In particular, Chapter 4 contains methods for solving recurrences, which are useful for describing the running times of recursive algorithms. One powerful technique is the “master method,” which can be used to solve recurrences that arise from divide-and-conquer algorithms. Much of Chapter 4 is devoted to proving the correctness of the master method, though this proof may be skipped without harm. Chapter 5 introduces probabilistic analysis and randomized algorithms. We typically use probabilistic analysis to determine the running time of an algorithm in cases in which, due to the presence of an inherent probability distribution, the running time may differ on different inputs of the same size. In some cases, we assume that the inputs conform to a known probability distribution, so that we are averaging the running time over all possible inputs. In other cases, the probability distribution comes not from the inputs but from random choices made during the course of the algorithm. An algorithm whose behavior is determined not only by its input but by the values produced by a random-number generator is a randomized algorithm. We can use randomized algorithms to enforce a probability distribution on the inputs—thereby ensuring that no particular input always causes poor performance—or even to bound the error rate of algorithms that are allowed to produce incorrect results on a limited basis. Appendices A–C contain other mathematical material that you will find helpful as you read this book. You are likely to have seen much of the material in the appendix chapters before having read this book (although the specific notational conventions we use may differ in some cases from what you have seen in the past), and so you should think of the Appendices as reference material. On the other hand, you probably have not already seen most of the material in Part I. All the chapters in Part I and the Appendices are written with a tutorial flavor.

1 The Role of Algorithms in Computing

What are algorithms? Why is the study of algorithms worthwhile? What is the role of algorithms relative to other technologies used in computers? In this chapter, we will answer these questions.

1.1 Algorithms

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. We can also view an algorithm as a tool for solving a well-specified computa- tional problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship. For example, one might need to sort a sequence of numbers into nondecreasing order. This problem arises frequently in practice and provides fertile ground for introducing many standard design techniques and analysis tools. Here is how we formally define the sorting problem:

Input: A sequence of n numbers 〈a₁, a₂,…,an〉.

Output: A permutation (reordering) 〈a 1′ , a 2′ ,…,an ′ 〉 of the input sequence such that a 1′ ≤ a 2′ ≤···≤an ′.

For example, given the input sequence 〈31*,41,59,26,41,58〉, a sorting algorithm returns as output the sequence 〈26,31,41,41,58,*59〉. Such an input sequence is called an instance of the sorting problem. In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem. Sorting is a fundamental operation in computer science (many programs use it as an intermediate step), and as a result a large number of good sorting algorithms

Chapter 1 The Role of Algorithms in Computing

have been developed. Which algorithm is best for a given application depends on—among other factors—the number of items to be sorted, the extent to which the items are already somewhat sorted, possible restrictions on the item values, and the kind of storage device to be used: main memory, disks, or tapes. An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a correct algorithm solves the given computational problem. An incorrect algorithm might not halt at all on some input instances, or it might halt with an answer other than the desired one. Contrary to what one might expect, incorrect algorithms can sometimes be useful, if their error rate can be controlled. We shall see an example of this in Chapter 31 when we study algorithms for finding large prime numbers. Ordinarily, however, we shall be concerned only with correct algorithms. An algorithm can be specified in English, as a computer program, or even as a hardware design. The only requirement is that the specification must provide a precise description of the computational procedure to be followed.

What kinds of problems are solved by algorithms?

Sorting is by no means the only computational problem for which algorithms have been developed. (You probably suspected as much when you saw the size of this book.) Practical applications of algorithms are ubiquitous and include the following examples:

•The Human Genome Project has the goals of identifying all the 100,000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. Each of these steps requires sophisticated algorithms. While the solutions to the various problems involved are beyond the scope of this book, ideas from many of the chapters in this book are used in the solution of these biological problems, thereby enabling scientists to accomplish tasks while using resources efficiently. The savings are in time, both human and machine, and in money, as more information can be extracted from laboratory techniques. •The Internet enables people all around the world to quickly access and retrieve large amounts of information. In order to do so, clever algorithms are employed to manage and manipulate this large volume of data. Examples of problems which must be solved include finding good routes on which the data will travel (techniques for solving such problems appear in Chapter 24), and using a search engine to quickly find pages on which particular information resides (related techniques are in Chapters 11 and 32).

1.1 Algorithms •Electronic commerce enables goods and services to be negotiated and exchanged electronically. The ability to keep information such as credit card numbers, passwords, and bank statements private is essential if electronic commerce is to be used widely. Public-key cryptography and digital signatures (covered in Chapter 31) are among the core technologies used and are based on numerical algorithms and number theory. •In manufacturing and other commercial settings, it is often important to allocate scarce resources in the most beneficial way. An oil company may wish to know where to place its wells in order to maximize its expected profit. A candidate for the presidency of the United States may want to determine where to spend money buying campaign advertising in order to maximize the chances of winning an election. An airline may wish to assign crews to flights in the least expensive way possible, making sure that each flight is covered and that government regulations regarding crew scheduling are met. An Internet service provider may wish to determine where to place additional resources in order to serve its customers more effectively. All of these are examples of problems that can be solved using linear programming, which we shall study in Chapter 29. While some of the details of these examples are beyond the scope of this book, we do give underlying techniques that apply to these problems and problem areas. We also show how to solve many concrete problems in this book, including the following: •We are given a road map on which the distance between each pair of adjacent intersections is marked, and our goal is to determine the shortest route from one intersection to another. The number of possible routes can be huge, even if we disallow routes that cross over themselves. How do we choose which of all possible routes is the shortest? Here, we model the road map (which is itself a model of the actual roads) as a graph (which we will meet in Chapter 10 and Appendix B), and we wish to find the shortest path from one vertex to another in the graph. We shall see how to solve this problem efficiently in Chapter 24. •We are given a sequence 〈A₁, A₂,…, A n 〉 of n matrices, and we wish to determine their product A₁ A₂ ···An. Because matrix multiplication is associative, there are several legal multiplication orders. For example, if n = 4, we could perform the matrix multiplications as if the product were parenthesized in any of the following orders: ( A₁( A₂( A₃ A₄))), ( A₁(( A₂ A₃) A₄)), (( A₁ A₂)( A₃ A₄)), (( A₁( A₂ A₃)) A₄),or*((( A₁A₂) A₃) A₄)*. If these matrices are all square (and hence the same size), the multiplication order will not affect how long the matrix multiplications take. If, however, these matrices are of differing sizes (yet their sizes are compatible for matrix multiplication), then the multiplication order can make a very big difference. The number of possible multiplication

Chapter 1 The Role of Algorithms in Computing

orders is exponential in n, and so trying all possible orders may take a very long time. We shall see in Chapter 15 how to use a general technique known as dynamic programming to solve this problem much more efficiently. •We are given an equation ax ≡ b (mod n),wherea, b,andn are integers, and we wish to find all the integers x, modulo n, that satisfy the equation. There may be zero, one, or more than one such solution. We can simply try x = 0*,1,…,n* − 1 in order, but Chapter 31 shows a more efficient method. •We are given n points in the plane, and we wish to find the convex hull of these points. The convex hull is the smallest convex polygon containing the points. Intuitively, we can think of each point as being represented by a nail sticking out from a board. The convex hull would be represented by a tight rubber band that surrounds all the nails. Each nail around which the rubber band makes a turn is a vertex of the convex hull. (See Figure 33.6 on page 948 for an example.) Any of the 2 n subsets of the points might be the vertices of the convex hull. Knowing which points are vertices of the convex hull is not quite enough, either, since we also need to know the order in which they appear. There are many choices, therefore, for the vertices of the convex hull. Chapter 33 gives two good methods for finding the convex hull.

These lists are far from exhaustive (as you again have probably surmised from this book’s heft), but exhibit two characteristics that are common to many interesting algorithms.

1. There are many candidate solutions, most of which are not what we want. Finding one that we do want can present quite a challenge.
2. There are practical applications. Of the problems in the above list, shortest paths provides the easiest examples. A transportation firm, such as a trucking or railroad company, has a financial interest in finding shortest paths through a road or rail network because taking shorter paths results in lower labor and fuel costs. Or a routing node on the Internet may need to find the shortest path through the network in order to route a message quickly.

Data structures

This book also contains several data structures. A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them.

1.1 Algorithms

Technique

Although you can use this book as a “cookbook” for algorithms, you may someday encounter a problem for which you cannot readily find a published algorithm (many of the exercises and problems in this book, for example!). This book will teach you techniques of algorithm design and analysis so that you can develop algorithms on your own, show that they give the correct answer, and understand their efficiency.

Hard problems

Most of this book is about efficient algorithms. Our usual measure of efficiency is speed, i.e., how long an algorithm takes to produce its result. There are some problems, however, for which no efficient solution is known. Chapter 34 studies an interesting subset of these problems, which are known as NP-complete. Why are NP-complete problems interesting? First, although no efficient algorithm for an NP-complete problem has ever been found, nobody has ever proven that an efficient algorithm for one cannot exist. In other words, it is unknown whether or not efficient algorithms exist for NP-complete problems. Second, the set of NP-complete problems has the remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. This relationship among the NP-complete problems makes the lack of efficient solutions all the more tantalizing. Third, several NP-complete problems are similar, but not identical, to problems for which we do know of efficient algorithms. A small change to the problem statement can cause a big change to the efficiency of the best known algorithm. It is valuable to know about NP-complete problems because some of them arise surprisingly often in real applications. If you are called upon to produce an efficient algorithm for an NP-complete problem, you are likely to spend a lot of time in a fruitless search. If you can show that the problem is NP-complete, you can instead spend your time developing an efficient algorithm that gives a good, but not the best possible, solution. As a concrete example, consider a trucking company with a central warehouse. Each day, it loads up the truck at the warehouse and sends it around to several locations to make deliveries. At the end of the day, the truck must end up back at the warehouse so that it is ready to be loaded for the next day. To reduce costs, the company wants to select an order of delivery stops that yields the lowest overall distance traveled by the truck. This problem is the well-known “traveling-salesman problem,” and it is NP-complete. It has no known efficient algorithm. Under certain assumptions, however, there are efficient algorithms that give an overall distance that is not too far above the smallest possible. Chapter 35 discusses such “approximation algorithms.”

Chapter 1 The Role of Algorithms in Computing

Exercises

1.1-1

Give a real-world example in which one of the following computational problems appears: sorting, determining the best order for multiplying matrices, or finding the convex hull.

1.1-2

Other than speed, what other measures of efficiency might one use in a real-world setting?

1.1-3

Select a data structure that you have seen previously, and discuss its strengths and limitations.

1.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?

1.1-5

Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough.

1.2 Algorithms as a technology

Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms? The answer is yes, if for no other reason than that you would still like to demonstrate that your solution method terminates and does so with the correct answer. If computers were infinitely fast, any correct method for solving a problem would do. You would probably want your implementation to be within the bounds of good software engineering practice (i.e., well designed and documented), but you would most often use whichever method was the easiest to implement. Of course, computers may be fast, but they are not infinitely fast. And memory may be cheap, but it is not free. Computing time is therefore a bounded resource, and so is space in memory. These resources should be used wisely,