Algorithms Copyright c 2006 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (cid:13) July 18, 2006 2 Algorithms Contents Preface 9 0 Prologue 11 0.1 Books andalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 0.2 Enter Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 0.3 Big-O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1 Algorithmswith numbers 21 1.1 Basicarithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2 Modulararithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.3 Primalitytesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5 Universalhashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Randomizedalgorithms: a virtualchapter 39 2 Divide-and-conquer algorithms 55 2.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.3 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.4 Medians. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.5 Matrixmultiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.6 Thefast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3 Decompositionsof graphs 91 3.1 Whygraphs? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.2 Depth-(cid:2)rst search inundirected graphs . . . . . . . . . . . . . . . . . . . . . . . . 93 3.3 Depth-(cid:2)rst search indirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.4 Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3 4 Algorithms 4 Paths in graphs 115 4.1 Distances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.2 Breadth-(cid:2)rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.3 Lengthsonedges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.4 Dijkstra’salgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.5 Priority queueimplementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.6 Shortest pathsinthe presence of negativeedges . . . . . . . . . . . . . . . . . . . 128 4.7 Shortest pathsindags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5 Greedy algorithms 139 5.1 Minimumspanningtrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.2 Huffmanencoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 5.3 Horn formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 5.4 Set cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6 Dynamicprogramming 169 6.1 Shortest pathsindags,revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 6.2 Longest increasingsubsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 6.3 Edit distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.4 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.5 Chainmatrixmultiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 6.6 Shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 6.7 Independent sets intrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7 Linear programmingand reductions 201 7.1 Anintroduction to linearprogramming . . . . . . . . . . . . . . . . . . . . . . . . 201 7.2 Flowsinnetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 7.3 Bipartite matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 7.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 7.5 Zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.6 Thesimplexalgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 7.7 Postscript: circuit evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 8 NP-completeproblems 247 8.1 Search problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 8.2 NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8.3 Thereductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 S.Dasgupta,C.H.Papadimitriou,andU.V.Vazirani 5 9 CopingwithNP-completeness 283 9.1 Intelligentexhaustivesearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 9.2 Approximationalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 9.3 Localsearch heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 10 Quantum algorithms 311 10.1 Qubits,superposition, andmeasurement . . . . . . . . . . . . . . . . . . . . . . . 311 10.2 Theplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 10.3 ThequantumFouriertransform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 10.5 Quantumcircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 10.6 Factoring asperiodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.7 Thequantumalgorithmfor factoring . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Historicalnotes andfurther reading 331 Index 333 6 Algorithms List of boxes Basesandlogs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Two’scomplement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Is yoursocialsecurity numberaprime? . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Hey, thatwasgrouptheory! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Carmichaelnumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Randomizedalgorithms: avirtualchapter . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Anapplicationof numbertheory? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Binarysearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Annlognlower boundfor sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 TheUnixsortcommand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Whymultiplypolynomials? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Theslowspread of afast algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 How bigisyourgraph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Crawlingfast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Whichheapisbest? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 A randomizedalgorithmfor minimumcut . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Recursion? No, thanks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Programming? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Commonsubproblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 Of miceandmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Ontimeandmemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 A magictrick calledduality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Matrix-vector notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Visualizingduality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Gaussianelimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 7 8 Algorithms Linearprogramminginpolynomialtime . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Thestory of SissaandMoore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 WhyPandNP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 Thetwo waysto usereductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 Unsolvableproblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 TheFourier transform of aperiodic vector . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Setting upaperiodic superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 Quantumphysicsmeets computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 Preface Thisbookevolvedoverthepasttenyearsfromasetoflecturenotesdeveloped whileteaching the undergraduate Algorithms course at Berkeley and U.C. San Diego. Our way of teaching thiscourseevolvedtremendouslyovertheseyearsinanumberofdirections,partlytoaddress our students’ background (undeveloped formal skills outside of programming), and partly to re(cid:3)ect the maturing of the (cid:2)eld in general, as we have come to see it. The notes increasingly crystallized into a narrative, and we progressively structured the course to emphasize the (cid:147)story line(cid:148) implicit in the progression of the material. As a result, the topics were carefully selected and clustered. No attempt was made to be encyclopedic, and this freed us to include topics traditionallyde-emphasized or omitted from most Algorithmsbooks. Playing on the strengths of our students (shared by most of today’s undergraduates in Computer Science), instead of dwelling on formal proofs we distilled in each case the crisp mathematicalideathatmakesthealgorithmwork. Inotherwords,weemphasizedrigorover formalism. We found that our students were much more receptive to mathematical rigor of thisform. It isthisprogression of crisp ideasthathelpsweave the story. Once you think about Algorithms in this way, it makes sense to start at the historical be- ginning of it all, where, in addition, the characters are familiar and the contrasts dramatic: numbers, primality, and factoring. This is the subject of Part I of the book, which also in- cludes the RSA cryptosystem, and divide-and-conquer algorithms for integer multiplication, sortingandmedian(cid:2)nding,aswellasthefastFouriertransform. Therearethreeotherparts: Part II, the most traditional section of the book, concentrates on data structures and graphs; the contrast here isbetween the intricate structure of the underlyingproblems andthe short and crisp pieces of pseudocode that solve them. Instructors wishing to teach a more tradi- tional course can simply start with Part II, which is self-contained (following the prologue), and then cover Part I as required. In Parts I and II we introduced certain techniques (such as greedy and divide-and-conquer) which work for special kinds of problems; Part III deals with the (cid:147)sledgehammers(cid:148) of the trade, techniques that are powerful and general: dynamic programming (a novel approach helps clarify this traditional stumbling block for students) and linear programming (a clean and intuitive treatment of the simplex algorithm, duality, and reductions to the basic problem). The (cid:2)nal Part IV is about ways of dealing with hard problems: NP-completeness, various heuristics, as well as quantum algorithms, perhaps the most advanced and modern topic. As it happens, we end the story exactly where we started it, withShor’squantumalgorithmfor factoring. The book includes three additional undercurrents, in the form of three series of separate 9 10 Algorithms (cid:147)boxes,(cid:148) strengthening the narrative (and addressing variationsin the needs and interests of thestudents)whilekeepingthe(cid:3)owintact: piecesthatprovidehistoricalcontext;descriptions ofhowtheexplainedalgorithmsareusedinpractice(withemphasisoninternetapplications); andexcursionsfor themathematicallysophisticated.