Algorithms
Copyright ⃝c 2006 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani July 18, 2006
2 Algorithms
Copyright By PowCoder代写 加微信 powcoder
0 Prologue 11
0.1 Booksandalgorithms…………………………….. 11 0.2 EnterFibonacci ……………………………….. 12 0.3 Big-Onotation………………………………… 15 Exercises……………………………………… 18
1 Algorithms with numbers 21
1.1 Basicarithmetic……………………………….. 21 1.2 Modulararithmetic……………………………… 25 1.3 Primalitytesting ………………………………. 33 1.4 Cryptography ………………………………… 39 1.5 Universalhashing………………………………. 43 Exercises……………………………………… 48
Randomized algorithms: a virtual chapter 39
2 Divide-and-conquer algorithms 55
2.1 Multiplication ………………………………… 55 2.2 Recurrencerelations …………………………….. 58 2.3 Mergesort…………………………………… 60 2.4 Medians……………………………………. 64 2.5 Matrixmultiplication…………………………….. 66 2.6 ThefastFouriertransform………………………….. 68 Exercises……………………………………… 83
3 Decompositions of graphs 91
3.1 Whygraphs?…………………………………. 91 3.2 Depth-firstsearchinundirectedgraphs …………………… 93 3.3 Depth-firstsearchindirectedgraphs…………………….. 98 3.4 Stronglyconnectedcomponents………………………..101 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Algorithms
4 Paths in graphs 115
4.1 Distances……………………………………115 4.2 Breadth-firstsearch………………………………116 4.3 Lengthsonedges ……………………………….118 4.4 Dijkstra’salgorithm………………………………119 4.5 Priorityqueueimplementations………………………..126 4.6 Shortestpathsinthepresenceofnegativeedges . . . . . . . . . . . . . . . . . . .128 4.7 Shortestpathsindags …………………………….130 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5 Greedy algorithms 139
5.1 Minimumspanningtrees……………………………139 5.2 Huffmanencoding……………………………….153 5.3 Hornformulas…………………………………157 5.4 Setcover ……………………………………158 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6 Dynamic programming 169
6.1 Shortestpathsindags,revisited ……………………….169 6.2 Longestincreasingsubsequences……………………….170 6.3 Editdistance………………………………….174 6.4 Knapsack……………………………………181 6.5 Chainmatrixmultiplication………………………….184 6.6 Shortestpaths…………………………………186 6.7 Independentsetsintrees……………………………189 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7 Linear programming and reductions 201
7.1 Anintroductiontolinearprogramming ……………………201 7.2 Flowsinnetworks……………………………….211 7.3 Bipartitematching ………………………………219 7.4 Duality…………………………………….220 7.5 Zero-sumgames………………………………..224 7.6 Thesimplexalgorithm …………………………….227 7.7 Postscript:circuitevaluation …………………………236 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
8 NP-complete problems 247
8.1 Searchproblems………………………………..247 8.2 NP-completeproblems …………………………….257 8.3 Thereductions…………………………………262 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 5
9 Coping with NP-completeness 283
9.1 Intelligentexhaustivesearch …………………………284 9.2 Approximationalgorithms…………………………..290 9.3 Localsearchheuristics …………………………….297 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
10 Quantum algorithms 311
10.1Qubits,superposition,andmeasurement …………………..311 10.2Theplan ……………………………………315 10.3ThequantumFouriertransform ……………………….316 10.4Periodicity …………………………………..318 10.5Quantumcircuits ……………………………….321 10.6 Factoring as periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.7 The quantum algorithm for factoring . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
Historical notes and further reading 331 Index 333
6 Algorithms
List of boxes
Basesandlogs…………………………………… 21 Two’scomplement…………………………………. 27 Isyoursocialsecuritynumberaprime? ……………………… 33 Hey,thatwasgrouptheory! ……………………………. 36 Carmichaelnumbers ……………………………….. 37 Randomizedalgorithms:avirtualchapter…………………….. 39 Anapplicationofnumbertheory?…………………………. 40
Binarysearch …………………………………… 60 Annlognlowerboundforsorting…………………………. 62 TheUnixsortcommand …………………………….. 66 Whymultiplypolynomials? ……………………………. 68 Theslowspreadofafastalgorithm………………………… 82
Howbigisyourgraph?………………………………. 93 Crawlingfast ……………………………………105
Which heap is best? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Trees ………………………………………..140 A randomized algorithm for minimum cut . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Recursion? No, thanks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Programming? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Commonsubproblems ……………………………….177 Of mice and men . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 On time and memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
Amagictrickcalledduality …………………………….205 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Matrix-vectornotation ……………………………….211 Visualizingduality …………………………………222 Gaussian elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
Algorithms
Linear programming in polynomial time . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
ThestoryofSissaandMoore ……………………………247 Why P and NP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 Thetwowaystousereductions …………………………..259 Unsolvableproblems ………………………………..276
Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 The Fourier transform of a periodic vector . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Setting up a periodic superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 Quantumphysicsmeetscomputation ……………………….327
This book evolved over the past ten years from a set of lecture notes developed while teaching the undergraduate Algorithms course at Berkeley and U.C. San Diego. Our way of teaching this course evolved tremendously over these years in a number of directions, partly to address our students’ background (undeveloped formal skills outside of programming), and partly to reflect the maturing of the field 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 “story line” 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 traditionally de-emphasized or omitted from most Algorithms books.
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 mathematical idea that makes the algorithm work. In other words, we emphasized rigor over formalism. We found that our students were much more receptive to mathematical rigor of this form. It is this progression of crisp ideas that helps weave 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, sorting and median finding, as well as the fast Fourier transform. There are three other parts: Part II, the most traditional section of the book, concentrates on data structures and graphs; the contrast here is between the intricate structure of the underlying problems and the 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 “sledgehammers” 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 final 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, with Shor’s quantum algorithm for factoring.
The book includes three additional undercurrents, in the form of three series of separate 9
10 Algorithms
“boxes,” strengthening the narrative (and addressing variations in the needs and interests of the students) while keeping the flow intact: pieces that provide historical context; descriptions of how the explained algorithms are used in practice (with emphasis on internet applications); and excursions for the mathematically sophisticated.
Look around you. Computers and networks are everywhere, enabling an intricate web of com- plex human activities: education, commerce, entertainment, research, manufacturing, health management, human communication, even war. Of the two main technological underpinnings of this amazing proliferation, one is obvious: the breathtaking pace with which advances in microelectronics and chip design have been bringing us faster and faster hardware.
This book tells the story of the other intellectual enterprise that is crucially fueling the computer revolution: efficient algorithms. It is a fascinating story.
Gather ’round and listen close.
0.1 Books and algorithms
Two ideas changed the world. In 1448 in the German city of Mainz a goldsmith named Jo- hann Gutenberg discovered a way to print books by putting together movable metallic pieces. Literacy spread, the Dark Ages ended, the human intellect was liberated, science and tech- nology triumphed, the Industrial Revolution happened. Many historians say we owe all this to typography. Imagine a world in which only an elite could read these lines! But others insist that the key development was not typography, but algorithms.
Today we are so used to writing numbers in decimal, that it is easy to forget that Guten- berg would write the number 1448 as MCDXLVIII. How do you add two Roman numerals? What is MCDXLVIII + DCCCXII? (And just try to think about multiplying them.) Even a clever man like Gutenberg probably only knew how to add and subtract small numbers using his fingers; for anything more complicated he had to consult an abacus specialist.
The decimal system, invented in India around AD 600, was a revolution in quantitative reasoning: using only 10 symbols, even very large numbers could be written down compactly, and arithmetic could be done efficiently on them by following elementary steps. Nonetheless these ideas took a long time to spread, hindered by traditional barriers of language, distance, and ignorance. The most influential medium of transmission turned out to be a textbook, written in Arabic in the ninth century by a man who lived in Baghdad. Al Khwarizmi laid out the basic methods for adding, multiplying, and dividing numbers—even extracting square roots and calculating digits of π. These procedures were precise, unambiguous, mechanical,
12 Algorithms
efficient, correct—in short, they were algorithms, a term coined to honor the wise man after the decimal system was finally adopted in Europe, many centuries later.
Since then, this decimal positional system and its numerical algorithms have played an enormous role in Western civilization. They enabled science and technology; they acceler- ated industry and commerce. And when, much later, the computer was finally designed, it explicitly embodied the positional system in its bits and words and arithmetic unit. Scien- tists everywhere then got busy developing more and more complex algorithms for all kinds of problems and inventing novel applications—ultimately changing the world.
0.2 Enter Fibonacci
Al Khwarizmi’s work could not have gained a foothold in the West were it not for the efforts of one man: the 15th century Italian mathematician , who saw the potential of the positional system and worked hard to develop it further and propagandize it.
But today Fibonacci is most widely known for his famous sequence of numbers
0,1,1,2,3,5,8,13,21,34,…,
each the sum of its two immediate predecessors. More formally, the Fibonacci numbers Fn are
generated by the simple rule
Fn−1+Fn−2 ifn>1 Fn = 1 if n = 1
0 if n = 0 .
No other sequence of numbers has been studied as extensively, or applied to more fields: biology, demography, art, architecture, music, to name just a few. And, together with the powers of 2, it is computer science’s favorite sequence.
In fact, the Fibonacci numbers grow almost as fast as the powers of 2: for example, F30 is over a million, and F100 is already 21 digits long! In general, Fn ≈ 20.694n (see Exercise 0.3).
But what is the precise value of F100, or of F200? Fibonacci himself would surely have wanted to know such things. To answer, we need an algorithm for computing the nth Fibonacci number.
An exponential algorithm
One idea is to slavishly implement the recursive definition of Fn. Here is the resulting algo- rithm, in the “pseudocode” notation used throughout this book:
(n) function fib1
if n=0: return 0
if n=1: return 1
return fib1(n − 1) + fib1(n − 2)
Whenever we have an algorithm, there are three questions we always ask about it:
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 13
1. Is it correct?
2. How much time does it take, as a function of n? 3. And can we do better?
The first question is moot here, as this algorithm is precisely Fibonacci’s definition of Fn. But the second demands an answer. Let T(n) be the number of computer steps needed to compute fib1(n); what can we say about this function? For starters, if n is less than 2, the procedure halts almost immediately, after just a couple of steps. Therefore,
T(n)≤2 forn≤1.
For larger values of n, there are two recursive invocations of fib1, taking time T (n − 1) and T(n−2), respectively, plus three computer steps (checks on the value of n and a final addition).
Therefore,
T(n)=T(n−1)+T(n−2)+3 forn>1.
Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn.
This is very bad news: the running time of the algorithm grows as fast as the Fibonacci numbers! T(n) is exponential in n, which implies that the algorithm is impractically slow
except for very small values of n.
Let’s be a little more concrete about just how bad exponential time is. To compute F200,
the fib1 algorithm executes T (200) ≥ F200 ≥ 2138 elementary computer steps. How long this actually takes depends, of course, on the computer used. At this time, the fastest computer in the world is the NEC Earth Simulator, which clocks 40 trillion steps per second. Even on this machine, fib1(200) would take at least 292 seconds. This means that, if we start the computation today, it would still be going long after the sun turns into a red giant star.
But technology is rapidly improving—computer speeds have been doubling roughly every 18 months, a phenomenon sometimes called Moore’s law. With this extraordinary growth, perhaps fib1 will run a lot faster on next year’s machines. Let’s see—the running time of fib1(n) is proportional to 20.694n ≈ (1.6)n, so it takes 1.6 times longer to compute Fn+1 than Fn. And under Moore’s law, computers get roughly 1.6 times faster each year. So if we can reasonably compute F100 with this year’s technology, then next year we will manage F101. And the year after, F102. And so on: just one more Fibonacci number every year! Such is the curse of exponential time.
In short, our naive recursive algorithm is correct but hopelessly inefficient. Can we do better?
A polynomial algorithm
Let’s try to understand why fib1 is so slow. Figure 0.1 shows the cascade of recursive invo- cations triggered by a single call to fib1(n). Notice that many computations are repeated!
A more sensible scheme would store the intermediate results—the values F 0 , F1 , . . . , Fn−1 — as soon as they become known.
Figure 0.1 The proliferation of recursive calls in fib1.
Algorithms
Fn−3 Fn−4 Fn−4 Fn−5
Fn−4 Fn−5 Fn−5 Fn−6
(n) if n=0 return 0
function fib2
create an array f[0 . . . n] f[0] =0,f[1] =1
for i = 2 . . . n:
f[i] = f[i − 1] + f[i − 2] return f[n]
As with fib1, the correctness of this algorithm is self-evident because it directly uses the definition of Fn. How long does it take? The inner loop consists of a single computer step and is executed n − 1 times. Therefore the number of computer steps used by fib2 is linear in n. From exponential we are down to polynomial, a huge breakthrough in running time. It is now perfectly reasonable to compute F200 or even F200,000.1
As we will see repeatedly throughout this book, the right algorithm makes all the differ- ence.
More careful analysis
In our discussion so far, we have been counting the number of basic computer steps executed by each algorithm and thinking of these basic steps as taking a constant amount of time. This is a very useful simplification. After all, a processor’s instruction set has a variety of basic primitives—branching, storing to memory, comparing numbers, simple arithmetic, and
1To better appreciate the importance of this dichotomy between exponential and polynomial
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com