Texts and Monographs in Computer Science Editor David Gries Advisory Board F.L. Bauer S.D. Brookes C.E. Leiserson F.B. Schneider M. Sipser Texts and Monographs in Computer Science Suad Alagic, Object-Oriented Database Programming Suad Alagic, Relational Database Technology Suad Alagic and Michael A Arbib, The Design of Well-Structured and Correct Programs S. Thomas Alexander, Adaptive Signal Processing: Theory and Applications Krzysztof R. Apt and Ernst-Rudiger Olderog, Verification of Sequential and Concurrent Programs Michael A Arbib, A.J. Kfoury, and Robert N. Moll, A Basis for Theoretical Computer Science Friedrich L. Bauer and Hans Wossner, Algorithmic Language and Program Development W. Bischofberger and G. Pomberger, Prototyping-Oriented Software Development: Concepts and Tools Ronald V. Book and Friedrich Otto, String-Rewriting Systems Kaare Christian, A Guide to Modula-2 Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective Edsger W. Dijkstra and Carel S. Scholten, Predicate Calculus and Program Semantics W.H.J. Feijen, AJ.M. van Gasteren, D. Gries, and J. Misra, Eds., Beauty Is Our Business: A Birthday Salute to Edsger W. Dijkstra PA Fejer and DA Simovici, Mathematical Foundations of Computer Science, Volume I: Sets, Relations, and Induction Melvin Fitting, First-Order Logic and Automated Theorem Proving Nissim Francez, Fairness R.T. Gregory and E.V. Krishnamurthy, Methods and Applications of Error-Free Computation David Gries, Ed., Programming Methodology: A Collection of Articles by Members of IFIP WG2.3 David Gries, The Science of Programming David Gries and Fred B. Schneider, A Logical Approach to Discrete Math (continued after index) The Design and Analysis of Algorithms Dexter C. Kazen With 72 Illustrations , Springer Dexter C. Kozen Series Editor: Department of Computer Science David Gries Cornell University Department of Computer Science Upson Hall Cornell University Ithaca, NY 14853-7501 Upson Hall USA Ithaca, NY 14853-7501 USA Library of Congress Cataloging-in-Publication Data Kozen, Dexter, 1951- The design and analysis of algorithms / Dexter C. Kozen. p. cm. Includes bibliographical references and index. ISBN-13: 978-1-4612-8757-5 e-ISBN-13: 978-1-4612-4400-4 DOl: 10.1007/978-1-4612-4400-4 1. Computer algorithms. I. Title. QA76.9.A43K69 1991 005.1-dc20 91-38759 Printed on acid-free paper. © 1992 Springer-Verlag New York, Inc. Softcover reprint of the hardcover 1s t edition 1992 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or here after developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Production managed by Bill Imbornoni; rnanufacturing supervised by Jacqui Ashri. Photocomposed from a LaTeX file. 9 8 7 6 5 Springer-Verlag New York Berlin Heidelberg A member of Berte/smannSpringer Science+Business Media GmbH To my wife Frances and my sons Alexander, Geoffrey, and Timothy Preface These are my lecture notes from CS681: Design and Analysis of Algo rithms, a one-semester graduate course I taught at Cornell for three consec utive fall semesters from '88 to '90. The course serves a dual purpose: to cover core material in algorithms for graduate students in computer science preparing for their PhD qualifying exams, and to introduce theory students to some advanced topics in the design and analysis of algorithms. The material is thus a mixture of core and advanced topics. At first I meant these notes to supplement and not supplant a textbook, but over the three years they gradually took on a life of their own. In addition to the notes, I depended heavily on the texts • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975. • M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. w. H. Freeman, 1979. • R. E. Tarjan, Data Structures and Network Algorithms. SIAM Regional Conference Series in Applied Mathematics 44, 1983. and still recommend them as excellent references. The course consists of 40 lectures. The notes from these lectures were prepared using scribes. At the beginning of each lecture, I would assign a scribe who would take notes for the entire class and prepare a raw :M\TEiX source, which I would then doctor and distribute. In addition to the 40 lec tures, I have included 10 homework sets and several miscellaneous homework exercises, all with complete solutions. The notes that were distributed are essentially as they appear here; no major reorganization has been attempted. There is a wealth of interesting topics, both classical and current, that I would like to have touched on but could not for lack of time. Many of these, such as computational geometry and factoring algorithms, could fill an entire semester. Indeed, one of the most difficult tasks was deciding how best to spend a scant 40 lectures. I wish to thank all the students who helped prepare these notes and who kept me honest: Mark Aagaard, Mary Ann Branch, Karl-Friedrich B6hringer, Thomas Bressoud, Suresh Chari, Sofoklis Efremidis, Ronen Feldman, Ted vii Fischer, Richard Huff, Michael Kalantar, Steve Kautz, Dani Lischinski, Pe ter Bro Miltersen, Marc Parmet, David Pearson, Dan Proskauer, Uday Rao, Mike Reiter, Gene Ressler, Alex Russell, Laura Sabel, Aravind Srinivasan, Sridhar Sundaram, Ida Szafranska, Filippo Tampieri, and Sam Weber. I am especially indebted to my teaching assistants Mark Novick (fall '88), Alessan dro Panconesi (fall '89), and Kjartan Stefansson (fall '90) for their help with proofreading, preparation of solution sets, and occasional lecturing. I am also indebted to my colleagues Laszlo Babai, Gianfranco Bilardi, Michael Luby, Keith Marzullo, Erik Meineche Schmidt, Bernd Sturmfels, Eva Tardos, Steve Vavasis, Sue Whitesides, and Rich Zippel for valuable comments and interest ing exercises. Finally, I wish to express my sincerest gratitude to my colleague Vijay Vazirani, who taught the course in fall '87 and who was an invaluable source of help. I would be most grateful for any suggestions or criticism from readers. Cornell University Dexter Kozen Ithaca, NY December 1990 viii Contents Preface vii I Lectures 1 Algorithms and Their Complexity 3 2 Topological Sort and MST .... 9 3 Matroids and Independence . . . . 13 4 Depth-First and Breadth-First Search 19 5 Shortest Paths and Transitive Closure 25 6 Kleene Algebra. . . . . . 28 7 More on Kleene Algebra. 34 8 Binomial Heaps 40 9 Fibonacci Heaps . . . . 44 10 Union-Find ....... 48 11 Analysis of Union-Find 52 12 Splay Trees . . . . . . . 58 13 Random Search Trees . 65 14 Planar and Plane Graphs 71 15 The Planar Separator Theorem . 77 16 Max Flow ........ 84 17 More on Max Flow ... 90 18 Still More on Max Flow . 96 19 Matching ......... 101 20 More on Matching . . . . 106 21 Reductions and NP-Completeness 111 22 More on Reductions and NP-Completeness 116 23 More NP-Complete Problems. . . 122 24 Still More NP-Complete Problems 128 25 Cook's Theorem . . . . . . . . 134 26 Counting Problems and #P 138 27 Counting Bipartite Matchings 144 28 Parallel Algorithms and NC 151 29 Hypercubes and the Gray Representation 156 30 Integer Arithmetic in NC 160 31 Csanky's Algorithm . . . . ..... 166 ix 32 Chistov's Algorithm . . . . . . . . . . . . 171 33 Matrix Rank . . . . . . . . . . . . . . . . 176 34 Linear Equations and Polynomial GCDs . 181 35 The Fast Fourier Transform (FFT) . 186 36 Luby's Algorithm . . . . . . . 191 37 Analysis of Luby's Algorithm . . . 197 38 Miller's Primality Test ..... . 201 39 Analysis of Miller's Primality Test 206 40 Probabilistic Tests with Polynomials . 211 II Homework Exercises Homework 1 . 219 Homework 2. 220 Homework 3. 221 Homework 4. 222 Homework 5. 223 Homework 6. 224 Homework 7. 225 Homework 8. 226 Homework 9. 227 Homework 10 228 Miscellaneous Exercises . 230 III Homework Solutions Homework 1 Solutions 239 Homework 2 Solutions 242 Homework 3 Solutions 245 Homework 4 Solutions 250 Homework 5 Solutions 252 Homework 6 Solutions 254 Homework 7 Solutions 257 Homework 8 Solutions 260 Homework 9 Solutions 262 Homework 10 Solutions. 268 Solutions to Miscellaneous Exercises 272 Bibliography 301 Index 309 x I Lectures