442
Chapter9 GraphAlgorithms
9.36 multigraph isa graph inwhich multipleedges areallowed between pairs of
vertices.Whichofthealgorithmsinthischapterworkwithoutmodificationfor
multigraphs?Whatmodificationsneedtobedonefortheothers?
9.37
LetG= (V,E)beanundirectedgraph.Usedepth-firstsearchtodesignalinear
algorithmtoconvert eachedgeinGtoadirected edge such that theresulting
graphisstronglyconnected,ordeterminethatthisisnotpossible.
9.38 Youaregivena set ofsticks,which arelying ontopofeach otherinsome
configuration.Each stickisspecifiedbyitstwoendpoints;eachendpointisan
orderedtriplegivingitsx,y,andzcoordinates;nostickisvertical.Astickmaybe
pickeduponlyifthereisnostickontopofit.
a. Explain n how to o write a routine that takes s two o sticks and and reports
whetheraisabove,below,orunrelatedtob.(Thishasnothingtodowithgraph
theory.)
b.Giveanalgorithmthatdetermineswhetheritispossibletopickupallthesticks,
andifso,providesasequenceofstickpickupsthataccomplishesthis.
9.39 Agraphisk-colorableifeachvertexcanbegivenoneofkcolors,andnoedge
connectsidenticallycoloredvertices.Givealinear-timealgorithmtotestagraph
fortwo-colorability.Assumegraphsarestoredinadjacency-listformat;youmust
specifyanyadditionaldatastructuresthatareneeded.
9.40 Giveapolynomial-timealgorithmthatfindsV/2verticesthatcollectivelycover
atleastthree-fourths(3/4)oftheedgesinanarbitraryundirectedgraph.
9.41 Show how tomodifythe e topologicalsortalgorithmsothatifthegraphisnot
acyclic,thealgorithmwillprintoutsomecycle.Youmaynotusedepth-firstsearch.
9.42 LetGbeadirectedgraphwithNvertices.Avertexsiscalledasinkif,foreveryv
inVsuchthats=v,thereisanedge(v,s),andtherearenoedgesoftheform(s,v).
GiveanO(N)algorithmtodeterminewhetherornotGhasasink,assumingthat
Gisgivenbyitsn×nadjacencymatrix.
9.43 Whenavertexanditsincidentedgesareremovedfromatree,acollectionofsub-
treesremains.Givealinear-timealgorithmthatfindsavertexwhoseremovalfrom
anNvertextreeleavesnosubtreewithmorethanN/2vertices.
9.44 Givealinear-timealgorithmtodeterminethelongestunweightedpathinanacyclic
undirectedgraph(thatis,atree).
9.45 ConsideranN-by-Ngridinwhichsomesquaresareoccupiedbyblackcircles.Two
squaresbelongtothesamegroupiftheyshareacommonedge.InFigure9.88,
thereisonegroupoffouroccupiedsquares,threegroupsoftwooccupiedsquares,
andtwoindividualoccupiedsquares.Assumethatthegridisrepresentedbya
two-dimensionalarray.Writeaprogramthatdoesthefollowing:
a. Computesthesizeofagroupwhenasquareinthegroupisgiven.
b.Computesthenumberofdifferentgroups.
c. Listsallgroups.
9.46 Section8.7describedthegeneratingofmazes.Supposewewanttooutputthepath
inthemaze.Assumethatthemazeisrepresentedasamatrix;eachcellinthematrix
storesinformationaboutwhatwallsarepresent(orabsent).
Convert pdf pages to powerpoint slides - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
converting pdf to powerpoint; adding pdf to powerpoint slide
Convert pdf pages to powerpoint slides - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
create powerpoint from pdf; convert pdf to powerpoint
Exercises
443
Figure9.88 GridforExercise9.45
a. Writeaprogramthat computes enough h information tooutput apath in the
maze.Giveoutputintheform
SEN...
(representinggosouth,theneast,then
north,etc.).
b.IfyouareusingaC
++
compilerwithawindowingpackage,writeaprogram
thatdrawsthemazeand,atthepressofabutton,drawsthepath.
9.47 Supposethatwallsinthemazecanbeknockeddown,withapenaltyofPsquares.
Pisspecifiedasaparametertothealgorithm.(Ifthepenaltyis0,thentheproblem
istrivial.)Describeanalgorithmtosolvethisversionoftheproblem.Whatisthe
runningtimeforyouralgorithm?
9.48 Supposethatthemazemayormaynothaveasolution.
a. Describealinear-timealgorithmthatdeterminestheminimumnumberofwalls
thatneedtobeknockeddowntocreateasolution.(Hint:Useadouble-ended
queue.)
b.Describeanalgorithm(notnecessarilylinear-time)thatfindsashortestpath
afterknockingdowntheminimumnumberofwalls.Notethatthesolutionto
part (a)wouldgivenoinformationaboutwhichwallswouldbethebest to
knockdown.(Hint:UseExercise9.47.)
9.49 Writeaprogram to computeword d ladders wheresingle-charactersubstitutions
haveacostof1,andsingle-characteradditionsordeletionshaveacostofp>0,
specifiedbytheuser.AsmentionedattheendofSection9.3.6,thisisessentiallya
weightedshortest-pathproblem.
Explainhoweachofthefollowingproblems(Exercises9.50–9.53)canbesolvedby
applyingashortest-pathalgorithm.Thendesignamechanismforrepresentinganinput,
andwriteaprogramthatsolvestheproblem.
9.50 Theinputisalistofleaguegamescores(andtherearenoties).Ifallteamshaveat
leastonewinandaloss,wecangenerally“prove,”byasillytransitivityargument,
C# PowerPoint - How to Process PowerPoint
PowerPoint Document Processing Control in Visual C#.NET of RasterEdge .NET Imaging SDK is a reliable and professional PowerPoint slides/pages editing and
convert pdf file to powerpoint presentation; change pdf to powerpoint
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
clip art or screenshot to PowerPoint document slide large amount of robust PPT slides/pages editing methods & profession imaging controls, PDF document, image
convert pdf to ppt online; pdf to ppt
444
Chapter9 GraphAlgorithms
thatanyteamisbetterthananyother.Forinstance,inthesix-teamleaguewhere
everyoneplaysthreegames,supposewehavethefollowingresults:AbeatBand
C;BbeatCandF;CbeatD;DbeatE;EbeatA;FbeatDandE.Thenwecanprove
thatAisbetterthanF,becauseAbeatB,whointurn,beatF.Similarly,wecan
provethatFisbetterthanAbecauseFbeatEandEbeatA.Givenalistofgame
scoresandtwoteamsXandY,eitherfindaproof(ifoneexists)thatXisbetter
thanY,orindicatethatnoproofofthisformcanbefound.
9.51 Theinputisacollectionofcurrenciesandtheirexchangerates.Isthereasequence
ofexchangesthatmakesmoneyinstantly?Forinstance,ifthecurrenciesareX,Y,
andZandtheexchangerateis1Xequals2Ys,1Yequals2Zs,and1Xequals3
Zs,then300Zswillbuy100Xs,whichinturnwillbuy200Ys,whichinturnwill
buy400Zs.Wehavethusmadeaprofitof33percent.
9.52 Astudentneedstotakeacertainnumberofcoursestograduate,andthesecourses
haveprerequisitesthatmustbefollowed.Assumethatallcoursesareofferedevery
semesterandthatthestudentcantakeanunlimitednumberofcourses.Givenalist
ofcoursesandtheirprerequisites,computeaschedulethatrequirestheminimum
numberofsemesters.
9.53 TheobjectoftheKevinBaconGameistolinkamovieactortoKevinBaconvia
sharedmovieroles.Theminimumnumberoflinksisanactor’sBaconnumber.For
instance,TomHankshasaBaconnumberof1;hewasinApollo13 withKevin
Bacon.SallyFieldshasaBaconnumberof2,becauseshewasinForrestGumpwith
TomHanks,whowasinApollo13withKevinBacon.Almostallwell-knownactors
haveaBaconnumberof1or2.Assumethatyouhaveacomprehensivelistof
actors,withroles,3anddothefollowing:
a. Explainhowtofindanactor’sBaconnumber.
b.ExplainhowtofindtheactorwiththehighestBaconnumber.
c. Explainhowtofindtheminimumnumberoflinksbetweentwoarbitraryactors.
9.54 Thecliqueproblemcanbestatedasfollows:Givenanundirectedgraph,G=(V,E),
andaninteger,K,doesGcontainacompletesubgraphofatleastKvertices?
Thevertexcoverproblemcanbestatedasfollows:Givenanundirectedgraph,
= (V,E), and d an integer, K,does contain a subset V
⊂ such h that
|V
| ≤ KandeveryedgeinGhasavertexinV
?Showthatthecliqueproblem
ispolynomiallyreducibletovertexcover.
9.55 AssumethattheHamiltoniancycleproblemisNP-completeforundirectedgraphs.
a. ProvethattheHamiltoniancycleproblemisNP-completefordirectedgraphs.
b.Provethat the unweighted simplelongest-path problem is NP-complete for
directedgraphs.
9.56 Thebaseballcardcollectorproblemisasfollows:GivenpacketsP
1
,P
2
,...,P
M
,each
ofwhichcontainsasubsetoftheyear’sbaseballcards,andaninteger,K,isitpossi-
bletocollectallthebaseballcardsbychoosing≤Kpackets?Showthatthebaseball
cardcollectorproblemisNP-complete.
3
Forinstance,seetheInternetMovieDatabasefiles:
actor.list.gz
and
actresses.list.gz
at
ftp://ftp.fu-berlin.de/pub/misc/movies/database
.
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
add image to slide, extract slides and merge library SDK, this VB.NET PowerPoint processing control powerful & profession imaging controls, PDF document, image
how to convert pdf to powerpoint slides; pdf page to powerpoint
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
Besides, users also can get the precise PowerPoint slides count as soon as the PowerPoint document has been loaded by using the page number getting method.
adding pdf to powerpoint; pdf to ppt converter
References
445
References
Good graphtheorytextbooksinclude[9],[14],[24],and[39].Moreadvancedtopics,
includingthemorecarefulattentiontorunningtimes,arecoveredin[41],[44],and[51].
Useofadjacencylistswasadvocatedin[26].Thetopologicalsortalgorithmisfrom
[31],asdescribedin[36].Dijkstra’salgorithmappearedin[10].Theimprovementsusing
d-heapsandFibonacciheapsaredescribedin[30]and[16],respectively.Theshortest-path
algorithmwithnegativeedgeweightsisduetoBellman[3];Tarjan[51]describesamore
efficientwaytoguaranteetermination.
FordandFulkerson’sseminalworkonnetworkflowis[15].Theideaofaugmenting
alongshortestpathsoronpathsadmittingthelargestflowincreaseisfrom[13].Other
approachestotheproblemcanbefoundin[11],[34],[23],[7],[35],[22],and[43].An
algorithmforthemin-costflowproblemcanbefoundin[20].
Anearlyminimumspanningtreealgorithmcanbefoundin[4].Prim’salgorithmis
from[45];Kruskal’salgorithmappearsin[37].TwoO(|E|loglog|V|)algorithmsare[6]
and[52].Thetheoretically best-known algorithmsappearin[16],[18],[32]and [5].
AnempiricalstudyofthesealgorithmssuggeststhatPrim’salgorithm,implementedwith
decreaseKey
,isbestinpracticeonmostgraphs[42].
Thealgorithmforbiconnectivityisfrom[47].Thefirstlinear-timestrongcomponents
algorithm(Exercise9.28)appearsinthesamepaper.Thealgorithmpresentedinthetext
isduetoKosaraju(unpublished)andSharir[46].Otherapplicationsofdepth-firstsearch
appearin[27],[28],[48],and[49](asmentionedinChapter8,theresultsin[48]and
[49]havebeenimproved,butthebasicalgorithmisunchanged).
TheclassicreferenceworkforthetheoryofNP-completeproblemsis[21].Additional
materialcanbefoundin[1].TheNP-completenessofsatisfiabilityisshownin[8]andinde-
pendentlybyLevin.Theotherseminalpaperis[33],whichshowedtheNP-completeness
of21problems.Anexcellentsurveyofcomplexitytheoryis[50].Anapproximationalgo-
rithmforthetravelingsalesmanproblem,whichgenerallygivesnearlyoptimalresults,can
befoundin[40].
Asolution toExercise9.8canbefoundin[2].Solutionstothebipartitematching
probleminExercise9.13canbefoundin[25]and[38].Theproblemcanbegeneralized
byaddingweightstotheedgesandremovingtherestrictionthatthegraphisbipartite.
Efficient solutions for theunweighted matching problem for generalgraphsarequite
complex.Detailscanbefoundin[12],[17],and[19].
Exercise9.35dealswith planargraphs,whichcommonly arise in practice.Planar
graphsareverysparse,andmanydifficultproblemsareeasieronplanargraphs.Anexam-
pleisthegraphisomorphismproblem,whichissolvableinlineartimeforplanargraphs
[29].Nopolynomialtimealgorithmisknownforgeneralgraphs.
1.A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,TheDesignandAnalysisofComputerAlgorithms,
Addison-Wesley,Reading,Mass.,1974.
2.R.K.Ahuja,K.Melhorn,J.B.Orlin,andR.E.Tarjan,“FasterAlgorithmsfortheShortest
PathProblem,”JournaloftheACM,37(1990),213–223.
3.R.E.Bellman,“OnaRoutingProblem,”QuarterlyofAppliedMathematics,16(1958),87–90.
4.O.Borˇuvka,“Ojistémproblémuminimálním(OnaMinimalProblem),”PrácaMoravské
P˘rirodo-v˘edeckéSpole˘cnosti,3(1926),37–58.
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
pages of document 1 and some pages of document please read this VB.NET PowerPoint slide processing powerful & profession imaging controls, PDF document, image
pdf to powerpoint; convert pdf to powerpoint slide
VB.NET PowerPoint: Merge and Split PowerPoint Document(s) with PPT
of the split PPT document will contain slides/pages 1-4 code in VB.NET to finish PowerPoint document splitting If you want to see more PDF processing functions
embed pdf into powerpoint; pdf to ppt converter online
446
Chapter9 GraphAlgorithms
5.B.Chazelle,“AMinimumSpanningTreeAlgorithmwithInverse-AckermannTypeCom-
plexity,”JournaloftheACM,47(2000),1028–1047.
6.D.CheritonandR.E.Tarjan,“FindingMinimumSpanningTrees,”SIAMJournalonCom-
puting,5(1976),724–742.
7.J.CheriyanandT.Hagerup,“ARandomizedMaximum-FlowAlgorithm,”SIAMJournalon
Computing,24(1995),203–226.
8.S.Cook,“TheComplexityofTheoremProvingProcedures,”ProceedingsoftheThirdAnnual
ACMSymposiumonTheoryofComputing(1971),151–158.
9.N.Deo,GraphTheorywithApplicationstoEngineeringandComputerScience,PrenticeHall,
EnglewoodCliffs,N.J.,1974.
10.E.W.Dijkstra,“ANoteonTwoProblemsinConnexionwithGraphs,”NumerischeMathe-
matik,1(1959),269–271.
11.E.A.Dinic,“AlgorithmforSolutionof aProblemofMaximumFlowinNetworkswith
PowerEstimation,”SovietMathematicsDoklady,11(1970),1277–1280.
12.J. Edmonds, “Paths, , Trees, , and Flowers,” ” CanadianJournal of Mathematics, 17 7 (1965),
449–467.
13.J. Edmonds and R. M. . Karp, , “Theoretical Improvements inAlgorithmic Efficiency for
NetworkFlowProblems,”JournaloftheACM,19(1972),248–264.
14.S.Even,GraphAlgorithms,ComputerSciencePress,Potomac,Md.,1979.
15.L.R.Ford,Jr.,andD.R.Fulkerson,FlowsinNetworks,PrincetonUniversityPress,Princeton,
N.J.,1962.
16.M.L.FredmanandR.E.Tarjan,“FibonacciHeapsandTheirUsesinImprovedNetwork
OptimizationAlgorithms,”JournaloftheACM,34(1987),596–615.
17.H.N.Gabow,“DataStructuresforWeightedMatchingandNearestCommonAncestorswith
Linking,”ProceedingsofFirstAnnualACM-SIAMSymposiumonDiscreteAlgorithms(1990),
434–443.
18.H.N.Gabow,Z.Galil,T.H.Spencer,andR.E.Tarjan,“EfficientAlgorithmsforFinding
MinimumSpanningTreesonDirectedandUndirectedGraphs,”Combinatorica,6(1986),
109–122.
19.Z.Galil,“EfficientAlgorithmsforFindingMaximumMatchingsinGraphs,”ACMComputing
Surveys,18(1986),23–38.
20.Z.GalilandE.Tardos,“AnO(n2(m+nlogn)logn)Min-CostFlowAlgorithm,”Journalof
theACM,35(1988),374–386.
21.M. R. . Garey and D. . S. . Johnson, Computers andIntractability:A Guide to the Theory of
NP-Completeness,Freeman,SanFrancisco,1979.
22.A.V.GoldbergandS.Rao,“BeyondtheFlowDecompositionBarrier,”JournaloftheACM,
45(1998),783–797.
23.A.V.GoldbergandR.E.Tarjan,“ANewApproachtotheMaximum-FlowProblem,”Journal
oftheACM,35(1988),921–940.
24.F.Harary,GraphTheory,Addison-Wesley,Reading,Mass.,1969.
25.J.E.HopcroftandR.M.Karp,“Ann5/2 AlgorithmforMaximumMatchingsinBipartite
Graphs,”SIAMJournalonComputing,2(1973),225–231.
26.J.E.HopcroftandR.E.Tarjan,“Algorithm447:EfficientAlgorithmsforGraphManipu-
lation,”CommunicationsoftheACM,16(1973),372–378.
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
VB.NET PowerPoint Conversion Control to render and convert target PowerPoint document to various image or document formats, such as PDF, BMP, TIFF
and paste pdf into powerpoint; convert pdf slides to powerpoint
VB.NET PowerPoint: Convert & Render PPT into PDF Document
Using this VB.NET PowerPoint to PDF converting demo code below, you can easily convert all slides of source PowerPoint document into a multi-page PDF file.
how to convert pdf slides to powerpoint presentation; conversion of pdf to ppt online
References
447
27.J.E.HopcroftandR.E.Tarjan,“DividingaGraphintoTriconnectedComponents,”SIAM
JournalonComputing,2(1973),135–158.
28.J.E.HopcroftandR.E.Tarjan,“EfficientPlanarityTesting,”JournaloftheACM,21(1974),
549–568.
29.J. E. . Hopcroft t and J. . K. . Wong, “Linear-Time Algorithm m for Isomorphism of Planar
Graphs,”ProceedingsoftheSixthAnnualACMSymposiumonTheoryofComputing(1974),
172–184.
30.D.B.Johnson,“EfficientAlgorithmsforShortestPathsinSparseNetworks,”Journalofthe
ACM,24(1977),1–13.
31.A.B.Kahn,“TopologicalSortingofLargeNetworks,”CommunicationsoftheACM,5(1962),
558–562.
32.D.R.Karger,P.N.Klein,andR.E.Tarjan,“ARandomizedLinear-TimeAlgorithmtoFind
MinimumSpanningTrees,”JournaloftheACM,42(1995),321–328.
33.R.M.Karp,“ReducibilityamongCombinatorialProblems,”ComplexityofComputerCompu-
tations(eds.R.E.MillerandJ.W.Thatcher),PlenumPress,NewYork,1972,85–103.
34.A.V.Karzanov,“DeterminingtheMaximalFlowinaNetworkbytheMethodofPreflows,”
SovietMathematicsDoklady,15(1974),434–437.
35.V.King,S.Rao,andR.E.Tarjan,“AFasterDeterministicMaximumFlowAlgorithm,”Jour-
nalofAlgorithms,17(1994),447–474.
36.D. E.Knuth, TheArtofComputer Programming,Vol.1:FundamentalAlgorithms, 3d ed.,
Addison-Wesley,Reading,Mass.,1997.
37.J.B.Kruskal,Jr.,“OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesman
Problem,”ProceedingsoftheAmericanMathematicalSociety,7(1956),48–50.
38.H.W.Kuhn,“TheHungarianMethodfortheAssignmentProblem,”NavalResearchLogistics
Quarterly,2(1955),83–97.
39.E. L. . Lawler, Combinatorial Optimization: Networks and d Matroids, Holt, Reinhart and
Winston,NewYork,1976.
40.S.LinandB.W.Kernighan,“AnEffectiveHeuristicAlgorithmfortheTravelingSalesman
Problem,”OperationsResearch,21(1973),498–516.
41.K. Melhorn, Data Structures and d Algorithms s 2: Graph h Algorithms s and d NP-completeness,
Springer-Verlag,Berlin,1984.
42.B.M.E.MoretandH.D.Shapiro,“AnEmpiricalAnalysisofAlgorithmsforConstructing
a MinimumSpanningTree,” Proceedings oftheSecondWorkshoponAlgorithms andData
Structures(1991),400–411.
43.J.B.Orlin,“MaxFlowsinO(nm)Time,orBetter,”ProceedingsoftheForty-fifthAnnualACM
SymposiumonTheoryofComputing(2013).
44.C.H.PapadimitriouandK.Steiglitz,CombinatorialOptimization:AlgorithmsandComplexity,
PrenticeHall,EnglewoodCliffs,N.J.,1982.
45.R.C.Prim,“ShortestConnectionNetworksandSomeGeneralizations,”BellSystemTechnical
Journal,36(1957),1389–1401.
46.M.Sharir,“AStrong-ConnectivityAlgorithmandIts ApplicationinDataFlowAnalysis,”
ComputersandMathematicswithApplications,7(1981),67–72.
47.R.E.Tarjan,“DepthFirstSearchandLinearGraphAlgorithms,”SIAMJournalonComputing,
1(1972),146–160.
C# PowerPoint: C# Guide to Add, Insert and Delete PPT Slide(s)
summary> /// Delete pages from PowerPoint view detailed guide for each PowerPoint slide processing powerful & profession imaging controls, PDF document, tiff
convert pdf document to powerpoint; convert pdf to editable ppt online
VB.NET PowerPoint: Read, Edit and Process PPTX File
VB.NET PowerPoint: Convert & Render PPTX Slide, VB.NET PowerPoint: Watermark PPTX Slide. How to convert PowerPoint to PDF, render PowerPoint to SVG
how to convert pdf to ppt online; changing pdf to powerpoint file
448
Chapter9 GraphAlgorithms
48.R.E.Tarjan,“TestingFlowGraphReducibility,”JournalofComputerandSystemSciences,9
(1974),355–365.
49.R. E. Tarjan,“Finding Dominators in DirectedGraphs,” SIAMJournalonComputing,3
(1974),62–89.
50.R. E. . Tarjan, , “Complexity y of Combinatorial Algorithms,” SIAM Review, 20 0 (1978),
457–491.
51.R. E.Tarjan, DataStructuresandNetworkAlgorithms,SocietyforIndustrialandApplied
Mathematics,Philadelphia,1983.
52.A.C.Yao,“AnO(|E|loglog|V|)AlgorithmforFindingMinimumSpanningTrees,”Informa-
tionProcessingLetters,4(1975),21–23.
C H H A A P T E R
10
AlgorithmDesign
Techniques
Sofar,wehavebeenconcernedwiththeefficientimplementationofalgorithms.Wehave
seenthatwhenanalgorithmisgiven,theactualdatastructuresneednotbespecified.It
isuptotheprogrammertochoosetheappropriatedatastructureinordertomakethe
runningtimeassmallaspossible.
Inthischapter,weswitchourattentionfromtheimplementationofalgorithmstothe
designofalgorithms.Mostofthealgorithmsthatwehaveseensofararestraightforwardand
simple.Chapter9containssomealgorithmsthataremuchmoresubtle,andsomerequire
anargument(insomecaseslengthy)toshowthattheyareindeedcorrect.Inthischapter,
wewillfocusonfiveofthecommontypesofalgorithmsusedtosolveproblems.Formany
problems,itisquitelikelythatatleastoneofthesemethodswillwork.Specifically,for
eachtypeofalgorithmwewill...
Seethegeneralapproach.
Lookatseveralexamples(theexercisesattheendofthechapterprovidemanymore
examples).
Discuss,ingeneralterms,thetimeandspacecomplexity,whereappropriate.
10.1 GreedyAlgorithms
Thefirsttypeofalgorithmwewillexamineisthegreedyalgorithm.Wehavealreadyseen
threegreedyalgorithmsinChapter9:Dijkstra’s,Prim’s,andKruskal’salgorithms.Greedy
algorithmsworkinphases.Ineachphase,adecisionismadethatappearstobegood,
withoutregardforfutureconsequences.Generally,thismeansthatsomelocaloptimumis
chosen.This“takewhatyoucangetnow”strategyisthesourceofthenameforthisclassof
algorithms.Whenthealgorithmterminates,wehopethatthelocaloptimumisequaltothe
globaloptimum.Ifthisisthecase,thenthealgorithmiscorrect;otherwise,thealgorithmhas
producedasuboptimalsolution.Iftheabsolutebestanswerisnotrequired,thensimple
greedyalgorithmsaresometimesusedtogenerateapproximateanswers,ratherthanusing
themorecomplicatedalgorithmsgenerallyrequiredtogenerateanexactanswer.
Thereareseveralreal-lifeexamplesofgreedyalgorithms.Themostobviousisthecoin-
changingproblem.TomakechangeinU.S.currency,werepeatedlydispensethelargest
449
450
Chapter10 AlgorithmDesignTechniques
denomination.Thus,togiveoutseventeendollarsandsixty-onecentsinchange,wegive
outaten-dollarbill,afive-dollarbill,twoone-dollarbills,twoquarters,onedime,and
onepenny.Bydoingthis,weareguaranteedtominimizethenumberofbillsandcoins.
Thisalgorithmdoesnotworkinallmonetarysystems,butfortunately,wecanprovethatit
doesworkintheAmericanmonetarysystem.Indeed,itworkseveniftwo-dollarbillsand
fifty-centpiecesareallowed.
Trafficproblemsprovideanexamplewheremakinglocallyoptimalchoicesdoesnot
alwayswork.Forexample,duringcertainrushhourtimesinMiami,itisbesttostayoff
theprimestreetseveniftheylookempty,becausetrafficwillcometoastandstillamile
downtheroad,andyouwillbestuck.Evenmoreshocking,itisbetterinsomecasesto
makeatemporarydetourinthedirectionoppositeyourdestinationinordertoavoidall
trafficbottlenecks.
Intheremainderofthissection,wewilllookatseveralapplicationsthatusegreedy
algorithms.Thefirst applicationisasimpleschedulingproblem.Virtually allschedul-
ingproblemsareeitherNP-complete(orofsimilardifficultcomplexity)oraresolvable
byagreedyalgorithm.Thesecondapplicationdealswithfilecompressionandisoneof
theearliestresultsincomputerscience.Finally,wewilllookatanexampleofagreedy
approximationalgorithm.
10.1.1 ASimpleSchedulingProblem
Wearegivenjobsj
1
,j
2
,...,j
N
,allwithknownrunningtimest
1
,t
2
,...,t
N
,respectively.
Wehaveasingleprocessor.Whatisthebestwaytoschedulethesejobsinordertomini-
mizetheaveragecompletiontime?Inthisentiresection,wewillassumenonpreemptive
scheduling:Onceajobisstarted,itmustruntocompletion.
Asanexample,supposewehavethefourjobsandassociatedrunningtimesshown
inFigure10.1.OnepossiblescheduleisshowninFigure10.2.Becausej
1
finishesin15
Job
Time
j
1
15
j
2
8
j
3
3
j
4
10
Figure10.1 Jobsandtimes
j
1
j
2
j
3
j
4
0
15
23 26
36
Figure10.2 Schedule#1
10.1 GreedyAlgorithms
451
j
3
j
2
j
4
j
1
0
3
11
21
36
Figure10.3 Schedule#2(optimal)
(timeunits),j
2
in23,j
3
in26,andj
4
in36,theaveragecompletiontimeis25.Abetter
schedule,whichyieldsameancompletiontimeof17.75,isshowninFigure10.3.
TheschedulegiveninFigure10.3isarrangedbyshortestjobfirst.Wecanshowthat
thiswillalwaysyieldanoptimalschedule.Letthejobsintheschedulebej
i
1
,j
i
2
,...,j
i
N
.
Thefirstjobfinishesintimet
i
1
.Thesecondjobfinishesaftert
i
1
+t
i
2
,andthethirdjob
finishesaftert
i
1
+t
i
2
+t
i
3
.Fromthis,weseethatthetotalcost,C,ofthescheduleis
C=
N
k=1
(Nk+1)t
i
k
(10.1)
C=(N+1)
N
k=1
t
i
k
N
k=1
k·t
i
k
(10.2)
NoticethatinEquation(10.2),thefirstsumisindependentofthejobordering,so
onlythesecondsumaffectsthetotalcost.Supposethatinanorderingthereexistssome
x>ysuchthatt
i
x
<t
i
y
.Thenacalculationshowsthatbyswappingj
i
x
andj
i
y
,thesecond
sumincreases,decreasingthetotalcost.Thus,anyscheduleofjobsinwhichthetimesare
notmonotonicallynondecreasingmustbesuboptimal.Theonlyschedulesleftarethosein
whichthejobsarearrangedbysmallestrunningtimefirst,breakingtiesarbitrarily.
This result t indicates s the e reason the e operating system m scheduler generally gives
precedencetoshorterjobs.
MultiprocessorCase
We can extend this problem m to o the e case of several processors. Again n we have e jobs
j
1
,j
2
,...,j
N
,withassociatedrunningtimest
1
,t
2
,...,t
N
,andanumberPofprocessors.
Wewillassumewithoutlossofgeneralitythatthejobsareordered,shortestrunningtime
first.Asanexample,supposeP=3,andthejobsareasshowninFigure10.4.
Figure10.5showsanoptimalarrangementtominimizemeancompletiontime.Jobs
j
1
,j
4
,andj
7
arerunonProcessor1.Processor2handlesj
2
,j
5
,andj
8
,andProcessor3runs
theremainingjobs.Thetotaltimetocompletionis165,foranaverageof
165
9
=18.33.
Thealgorithmtosolvethemultiprocessorcaseistostartjobsinorder,cyclingthrough
processors.Itisnothardtoshowthatnootherorderingcandobetter,althoughifthe
numberofprocessors,P,evenlydividesthenumberofjobs,N,therearemanyoptimal
orderings.Thisisobtainedby,foreach0≤i<N/P,placingeachofthejobsj
iP+1
through
j
(i+1)P
onadifferentprocessor.Inourcase,Figure10.6showsasecondoptimalsolution.
EvenifPdoesnotdivideNexactly,therecanstillbemanyoptimalsolutions,evenif
allthejobtimesaredistinct.Weleavefurtherinvestigationofthisasanexercise.
Documents you may be interested
Documents you may be interested