Divide-and-conquer algorithms - EECS at UC Berkeley

1 Chapter2 divide -and-conqueralgorithmsThedivide-an d-conquerstrategysolvesa ,inthreedifferentplaces:inthepartitionin gofproblemsintosubproblems;attheverytail endoftherecursion,whenthesubproblemsares osmallthattheyaresolvedoutright;andinthe gluingtogetherofpartialanswers. Theseareheldtogetherandcoordinatedbythea lgorithm's , we'llseehowthistechniqueyieldsa newalgorithmformulti-plyingnumbers, onethatis much moreef cientthanthemethodwealllearnedinelementa ryschool! Gauss(1777 1855)oncenoticedthatalthoughtheproductof twocomplexnumbers(a+bi)(c+di) =ac bd+ (bc+ad)iseemstoinvolvefourreal-numbermul tiplications, it caninfactbedonewithjustthree:ac,bd, and(a+b)(c+d), sincebc+ad=(a+b)(c+d) ac bd:Inourbig-Oway of thinking, reducingthenumberof multiplicationsfromfourtothreeseemswaste dingenuity. Butthismodestimprovementbecomesverysigni 's moveaway , andassumeforconveniencethatnis a powerof2(themoregeneralcaseis hardlyanydifferent).

2 Asa rststeptowardmultiplyingxandy,spliteach of themintotheirleftandrighthalves, which aren=2bitslong:x=xLxR= 2n=2xL+xRy=yLyR= 2n=2yL+ , ifx= 101101102(thesubscript2means binary )thenxL= 10112,xR= 01102,andx= 10112 24+ 01102. Theproductofxandycanthenberewrittenasxy= (2n=2xL+xR)(2n=2yL+yR) =2nxLyL+ 2n=2(xLyR+xRyL) +xRyR:We , asdothemultiplicationsbypowersof2(which aremerelyleft-shifts).Thesigni cantoperationsarethefourn=2-bitmultiplic ations,xLyL; xLyR; xRyL; xRyR; thesewecanhandlebyfourrecursivecalls. Thusourmethodformultiplyingn-bitnumberss tartsbymakingrecursivecallstomultiplythe sefourpairsofn=2-bitnumbers(foursubprobl emsofhalfthesize),andthenevaluatesthepre cedingexpressioninO(n)time. WritingT(n)fortheoverallrunningtimeonn-b itinputs, wegettherecurrencerelationT(n) = 4T(n=2) +O(n):We willsoonseegeneralstrategiesforsolvingsu ch equations.

3 Inthemeantime, thisparticu-laroneworksouttoO(n2), thesamerunningtimeasthetraditionalgrade- schoolmultiplica-tiontechnique. Sowehavea radicallynewalgorithm,butwehaven'tyetmad eanyprogressinef ciency. Howcanourmethodbespedup?ThisiswhereGauss 's trick , asbeforejustthreewilldo:xLyL;xRyR, and(xL+xR)(yL+yR),sincexLyR+xRyL= (xL+xR)(yL+yR) xLyL xRyR. Theresultingalgorithm, ,hasanimprovedrunningtimeof1T(n) = 3T(n=2) +O(n):Thepointis thatnowtheconstantfactorimprovement,from 4 to3, occursateverylevelof therecursion, andthiscompoundingeffectleadstoa dramaticallylowertimeboundofO(n1:59).Thi srunningtimecanbederivedbylookingattheal gorithm's patternofrecursivecalls,which forma treestructure, 's trytounderstandtheshapeof thistree. Ateach successivelevelofrecursionthesubproblems gethalvedinsize. Atthe(log2n)thlevel,1 Actually, therecurrenceshouldreadT(n) 3T(n=2 + 1) +O(n)sincethenumbers(xL+xR)and(yL+yR)cou ldben=2 + 1bitslong.

4 Theonewe'reusingis Dasgupta, , (x;y)Input:Positiveintegersxandy, in binaryOutput:Theirproductn=max(sizeofx, sizeofy)ifn= 1: returnxyxL,xR=leftmostdn=2e, rightmostbn=2cbitsofxyL,yR=leftmostdn=2e , rightmostbn=2cbitsofyP1=multiply(xL;yL)P 2=multiply(xR;yR)P3=multiply(xL+xR;yL+yR )returnP1 2n+ (P3 P1 P2) 2n=2+P2thesubproblemsgetdowntosize1, andsotherecursionends. Therefore, theheightofthetreeislog2n. Thebranchingfactoris3 each problemrecursivelyproducesthreesmalleron es withtheresultthatatdepthkinthetreetherea re3ksubproblems, each of sizen= subproblem,a linearamountofworkis doneinidentifyingfurthersubproblemsandco mbiningtheiranswers. Thereforethetotaltimespentatdepthkinthet reeis3k O n2k = 32 k O(n):Attheverytoplevel,whenk= 0, thisworksouttoO(n). Atthebottom,whenk= log2n,it isO(3log2n), which canberewrittenasO(nlog23)(doyouseewhy?)

5 Betweenthesetwoendpoints, theworkdoneincreasesgeometricallyfromO(n )toO(nlog23), bya factorof3= , withina constantfactor, simplythelasttermoftheseries:such istherapidityoftheincrease( ).ThereforetheoverallrunningtimeisO(nlog 23), which is aboutO(n1:59).IntheabsenceofGauss's trick,therecursiontreewouldhavethesamehe ight,butthebranchingfactorwouldbe4. Therewouldbe4log2n=n2leaves, , thenumberofsubprob-lemstranslatesintothe branchingfactorof therecursiontree;smallchangesinthiscoef cientcanhavea practicalnote:it generallydoesnotmakesensetorecurseallthe way , 16-or32-bitmultiplicationis a singleoperation, , theeternalquestion:Canwedobetter?Itturns outthatevenfasteralgorithmsformultiplyin gnumbersexist,basedonanotherimportantdiv ide-and-conqueralgorithm:thefastFouriert ransform, (a)Each problemis dividedintothreesubproblems. (b)Thelevelsof recursion.

6 (a)10110010 011000111011 01100010 00111101 1001(b)2111211121112111 SizenSizen=2 ..lognlevelsSizen= genericpattern:theytacklea problemofsizenbyrecursivelysolving, say,asubproblemsofsizen=bandthencombinin gtheseanswersinO(nd)time, forsomea;b;d >0(inthemultiplicationalgorithm,a= 3,b= 2, andd= 1). Theirrunningtimecanthereforebecapturedby theequationT(n) =aT(dn=be) +O(nd). We nextderivea closed-formsolutiontothisgeneralrecurren cesothatwenolongerhavetosolveitexplicitl yineach (n) =aT(dn=be) +O(nd)forsomeconstantsa >0,b >1, andd 0,2 Thereareevenmoregeneralresultsof thistype, Dasgupta, , problemof sizenis dividedintoasubproblemsof sizen= (n) =8<:O(nd)ifd >logbaO(ndlogn)ifd= logbaO(nlogba)ifd < provetheclaim,let's startbyassumingforthesakeofconvenienceth atnisapowerofb. Thiswillnotin uencethe nalboundinanyimportantway afterall,nisatmosta multiplicativefactorofbaway fromsomepowerofb( ) andit willallowustoignoretheroundingeffectindn = ,noticethatthesizeofthesubproblemsdecrea sesbya factorofbwitheach levelofrecursion,andthereforereachestheb asecaseafterlogbnlevels.

7 Thisistheheightoftherecursiontree. Itsbranchingfactorisa, sothekthlevelofthetreeismadeupofaksubpro blems, each of sizen=bk( ).Thetotalworkdoneatthislevelisak O nbk d=O(nd) abd k:Askgoesfrom0(theroot)tologbn(theleaves ),thesenumbersforma geometricserieswith60 Algorithmsratioa=bd. Findingthesumof such a seriesinbig-Onotationis easy( ), decreasing, anditssumis justgivenbyits rstterm,O(nd). increasinganditssumis givenbyitslastterm,O(nlogba):nd abd logbn=nd alogbn(blogbn)d =alogbn=a(logan)(logba)= (logn)termsof theseriesareequaltoO(nd). , ofcourse,binarysearch:to nda keykinalarge lecontainingkeysz[0;1;::: ;n 1]insortedorder, we rstcomparekwithz[n=2], anddependingontheresultwerecurseeitheron the rsthalfofthe le,z[0;::: ;n=2 1], oronthesecondhalf,z[n=2;::: ;n 1]. TherecurrencenowisT(n) =T(dn=2e) +O(1), which is thecasea= 1;b= 2;d= 0.

8 Pluggingintoourmastertheoremwegetthefami liarsolution:arunningtimeof justO(logn). listofnumberslendsitselfimmediatelytoa divide -and-conquerstrategy:splitthelisti ntotwohalves, recursivelysorteach half, (a[1:::n])Input:An arrayof numbersa[1:::n]Output:A sortedversionof thisarrayifn >1:returnmerge(mergesort(a[1:::bn=2c]), mergesort(a[bn=2c+ 1:::n]))else:returnaThecorrectnessofthis algorithmisself-evident,aslongasa correctmergesubroutineisspeci wearegiventwosortedarraysx[1:::k]andy[1: ::l], howdoweef cientlymergethemintoa singlesortedarrayz[1:::k+l]? Well,thevery rstelementofzis eitherx[1]ory[1], whicheveris smaller. Therestofz[ ] Dasgupta, , (x[1:::k];y[1::: l])ifk= 0: returny[1:::l]ifl= 0: returnx[1:::k]ifx[1] y[1]:returnx[1] merge(x[2:::k];y[1::: l])else:returny[1] merge(x[1:::k];y[2::: l])Here constantamountofworkperrecursivecall(pro videdtherequiredarray spaceis allocatedinadvance),fora totalrunningtimeofO(k+l).

9 Thusmerge's arelinear, andtheoveralltimetakenbymergesortisT(n) =2T(n=2) +O(n);orO(nlogn).Lookingback atthemergesortalgorithm,weseethatallther ealworkis doneinmerg-ing, which doesn'tstartuntiltherecursiongetsdowntos ingletonarrays. Thesingletonsaremergedinpairs, toyieldarrayswithtwoelements. Thenpairsofthese2-tuplesaremerged,produc ing4-tuples, Atanygivenmo-ment,thereis a setof active arrays initially, thesingletons which aremergedinpairstogivethenextbatch of activearrays. Thesearrayscanbeorganizedina queue, andprocessedbyrepeatedlyremovingtwoarray sfromthefrontofthequeue, mergingthem,andputtingtheresultattheendo f , theprimitiveoperationinjectaddsanelement totheendof thequeuewhileejectremovesandreturnstheel ementatthefrontof (a[1:::n])Input:elementsa1;a2;:::;anto be sortedQ= [ ](emptyqueue)fori= 1ton:inject(Q;[ai])whilejQj>1:inject(Q;m erge(eject(Q);eject(Q)))returneject(Q)S.

10 Dasgupta, , Vazirani63 AnnlognlowerboundforsortingSortingalgori thmscanbedepictedastrees. Theoneinthefollowing guresortsanarray ofthreeelements,a1;a2;a3. It startsbycomparinga1toa2and,if the rstis larger, comparesit witha3; otherwiseit comparesa2anda3. leaf, andthisleafis labeledwiththetrueorderofthethreeelement sasa permutationof1;2;3. Forexample, ifa2< a1< a3, wegettheleaflabeled 2 1 3. 3 2 1 Yesa2< a3?a1< a2?a1< a3?a2< a3?a1< a3?2 3 12 1 33 1 21 3 21 2 3 NoThedepthofthetree thenumberofcomparisonsonthelongestpathfr omroottoleaf,inthiscase3 isexactlytheworst-casetimecomplexityof oflookingatsortingalgorithmsisusefulbeca useit allowsonetoarguethatmergesortisoptimal, inthesensethat (nlogn) theargument:Consideranysuch treethatsortsanarray ofnelements. Each ofitsleavesis labeledbya permutationoff1;2;::: ;ng. Infact,everypermutationmustappearasthela belofa leaf.