Design and Analysis of Distributed Algorithms.pdf

i PREFACE tered in practice. This is particularly true of some of the matrix multiplication algorithms in Chapter 6, the Schonhage -Strasser integer-muitiphication algo rithm of Chapter 7, and some of the polynomial and integer algorithms of Chapter 8 On the other hand, most of the sorting algorithms of Chapter 3 the scarch inig algorithms of Chapter 4, the graph algorithms of Chapter 5, the fast Fourier transform of Chapter 7, and the string-matching algorithms of Chapter 9 are widely used, since the sizes of inputs for which these algorithms are efficient are sufficiently small to be encountered in many practical situations Chapters 10 through 12 discuss lower bounds on computational com plexity. The inherent computational difficulty of a problem is of universal interest both to program design and to an understanding of the nature of com putation. In Chapter 10 an important class of problems, the Np-complete probleins, is studied. All problems in this class are equivalent in computa- tional dificulty, in that if one problem in the class has an effcient (polynomial time-bounded)solution, then all problems in the class have eficient solutions Since this class of problems contains many practically important and well studied problems, such as the integer-programming problem and the traveling salesman problem, there is good reason to suspect that no problem in this class can be solved eficiently. Thus, if a program designer knows that the problem for which he is trying to find an efficient algorithm is in this class then he may very well be content to try heuristic approaches to the problem. In spite of the overwhelming empirical evidence to the contrary, it is still an cpen question whether NP-complete problems admit of efficient solutions In Chapter 1 l certain problems are defined for which we can actually prove that no efficient algorithms exist. the material in Chapters 10 and 11 draws heavily on the concept of Turing machines introduced in Sections 1. 6 and 1.7 In the final chapter of the book we relate concepts of computational dif- ficulty to notions of linear independence in vector spaces. The material in this chapter provides techniques for proving lower bounds for much simpler prob lems than those considered in Chapters 10 and 11 PREFACE V THE USE OF THE BOOK This book is intended as a first course in the design and analysis of algorithms The emphasis is on ideas and ease of understanding rather than implementa tion details or programming tricks. Informal intuitive explanations are often used in place of long tedious proofs. The book is self-contained and assumes no specific background in mathematics or programming languages. However, a certain amount of maturity in being able to handle mathematica! concepts is desirable, as is some exposure to a higher-level programming language such as FORTRAN or ALGOL. Some knowledge of linear algebra is needed for a full understanding of Chapters 6, 7, 8, and 12. This book has been used in graduate and undergraduate courses in algo rithm design. In a one-semester course most of Chapters 1-5 and 9-10 were covered, aiong with a smattering of topics from the remaining chapters. In introductory courses the emphasis was on material from Chapters 1-5, but Sections 1.6, 1.7,4. 13, 5.11, and Theorem 4.5 were generally not covered The book can also be used in more advanced courses emphasizing the theory of algorithms. Chapters 6-12 could serve as the foundation for such a course. Numerous exercises have been provided at the end of each chapter to provide an instructor with a wide range of home work problems The exercises are graded according to difficulty. Exercises with no stars are suitable for in- troductory courses, singly starred exercises for more advanced courses, and doubly starred exercises for advanced graduate courses. The bibliographic notes at the end of every chapter attempt to point to a published source for each of the algorithms and results contained in the text and the exercises ACKNOWLEDGMENTS The material in this book has been derived from class notes for courses taught by the authors at Cornell, Princeton, and stevens Institute of Technoiogy. the authors would like to thank the many people who have critically read various portions of the manuscript and offered many helpful suggestions. In particular we would like to thank Kellogg booth Stan Brown, Steve Chen, Allen Cypher. vI PREFACE Arch Davis, Mike Fischer, Hania Gajewska. Mike Garey, Udai Gupta. Mike Harrison, Matt Hecht, Harry Hunt, Dave Johnson, Marc Kaplan, Don Johnson, Steve Johnson, Brian Kernighan. Don Knuth, Richard Ladner, Anita LaSalle, Doug Mcllroy, Albert Meyer, Christos Papadimitr:ou, Bill Plauger, John Savage, Howard Siege!, Ken Steiglitz, I arry Stockmeyer, Tom Szymanski, and Theodore Yen Special thanks go to Gemma Carnevale, Pauline Cameron, Hannah Kresse, Edith Purser, and Ruth Suzuki for their cheerful and careful typing of the manuscript The authors are also grateful to Beil Laboratories and cornell, Princeton, and the University of California at Berkeley for providing facilities for the preparation of the manuscript. June 974 A.V. A .H J.D. U CONTENTS 1 Models of Computation 1 Algorithms and their complexity 1.2 Random access machines 1.3 Computational complexity of RAM programs 1. 4 A stored program model 1.5 Abstractions of the ram 19 1.6 A primitive model of computation: the Turing machine 25 1.7 Relationship between the Turing machine and ram models 3 1.8 Pidgin ALGOL,-a high-level language 33 2 Design of Eficient Algorithms 2.1 Data structures: lists, queues, and stacks 44 2.2 Set representations 49 23 Graphs∵ 50 2.4 Trees 52 2.5 Recursion 55 2.6 Divide-and-conquer 60 2.7 Balancing 65 2.8 Dynamic programming 67 2.9 Epilogue 69 3 Sorting and order statistics 3.1 The sorting problem 76 32 Radix sorting.、 77 3.3 Sorting by comparisons 86 3.4 Heapsort-an O(n log n)comparison sort 87 3.5 Quicksort-an O(n log n)expected time sort 92 3.6 Order statistics 97 3.7 Expected time for order statistics 100 4 Data Structures for Set Manipulation Problems 4.1 Fundamental operations on sets 108 42H ashing 4. 3 Binary search l13 4.4 Binary search trees 115 4.5 Optimal binary search trees 119 4. 6 A simple disjoint-set union algorithm 124 vill CONTENTS 4.7 Tree structures for the UNION-FIND problem 129 4.8 Applications and extensions of the union-FINd algorithm 139 4.9 Balanced tree schemes 145 4.10 Dictionaries and priority queues 48 4.11 Mergeable heaps 152 Concatenable queues 155 4. 13 Partitioning 157 4. 14 Chapter summary 162 5 Algorithms on Graphs 5. 1 Minimum-cost spanning trees 172 5.2 Depth-first search 176 5.3 Biconnectivity 179 5.4 Depth-first search of a directed graph 187 5.5 Strong connectivity 189 5.6 Path-finding problems 195 5.7 A transitive closure algorithm 199 5.8 a shortest-path algorithm 200 5.9 Path problems and matrix multiplication 201 5.10 Single-source problems 207 5. 1 1 Dominators in a directed acyclic graph: putting the concepts together. 209 6 Matrix Multiplication and Related Operations 6.1 Basics 226 6.2 Strassen's matrix-multiplication algorithm 230 6.3 Inversion of matrices 232 6.4 LUP decomposition of matrices 233 6.5 Applications of LUP decomposition 240 6.6 Boolean matrix multiplication 242 7 The Fast Fourier Transform and its applications 7.1 The discrete Fourier transform and its inverse ,252 7.2 The fast Fourier transform algorithm 257 7.3 The FfT using bit operations 265 7.4 Products of polynomials 269 7.5 The Schonhage-Strassen integer-multiplication algorithm 270 CONENix 8 Integer and Polynomial Arithmetic 8. 1 The similarity between integers and polynomials 278 8.2 Integer multiplication and division ,279 8.3 Polynomial multiplication and division 286 8. 4 Modular arithmetic 289 8.5 Modular polynomial arithmetic and polynomial evaluation 292 8.6 Chinese remaindering 294 8.7 Chinese remaindering and interpolation of polynomials 298 8.8 Greatest common divisors and euclids algorithm 300 8.9 An asymptotically fast algorithm for polynomial GCD's 303 8.10 Integer GCDs 308 8. 11 Chinese remaindering revisited 310 8.12 Sparse polynomials 31l1 9 Pattern-Matching algorithms 9. 1 Finite automata and regular expressions 318 9.2 Recognition of regular expression patterns 326 9.3 Recognition of substrings 329 9. 4 Two-way deterministic pushdown automata 335 9.5 Position trees and substring identifiers 346 10 NP-Complete Problems 10.1 Nondeterministic Turing machines 364 10.2 The classes and∥9 372 10.3 Languages and problems 374 10.4 NP-completeness of the satisfiability problem 377 10.5 Additional NP-complete problems 384 10.6 Polynomial-space-bounded problems 395 11 Some Provably Intractable Problems 11.1 Complexity hierarchies 406 1 1. 2 The space hierarchy for deterministic Turing machines 407 11.3 A problem requiring exponential time and space 410 11. 4 A nonelementary problem 419 CONTENT 12 Lower Bounds on Numbers of Arithmetic Operations 12.1 Fields 428 12.2 Straight-line code revisited 429 12.3 A matrix formulation of problems 432 12.4 A row-oriented lower bound on multiplications 432 12.5 A column-oriented lower bound on multiplications 435 12.6 A row-and- column-oriented bound on multiplications 439 12.7 Preconditioning 442 Bibliography 452 Index 463 MODELS OF COMPUTATION CHAPTER 1