﻿
442
Chapter9 GraphAlgorithms
9.36 multigraph isa graph inwhich multipleedges areallowed between pairs of
vertices.Whichofthealgorithmsinthischapterworkwithoutmodiﬁcationfor
multigraphs?Whatmodiﬁcationsneedtobedonefortheothers?
9.37
LetG= (V,E)beanundirectedgraph.Usedepth-ﬁrstsearchtodesignalinear
algorithmtoconvert eachedgeinGtoadirected edge such that theresulting
graphisstronglyconnected,ordeterminethatthisisnotpossible.
9.38 Youaregivena set ofsticks,which arelying ontopofeach otherinsome
conﬁguration.Each stickisspeciﬁedbyitstwoendpoints;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
9.40 Giveapolynomial-timealgorithmthatﬁndsV/2verticesthatcollectivelycover
atleastthree-fourths(3/4)oftheedgesinanarbitraryundirectedgraph.
9.41 Show how tomodifythe e topologicalsortalgorithmsothatifthegraphisnot
acyclic,thealgorithmwillprintoutsomecycle.Youmaynotusedepth-ﬁrstsearch.
inVsuchthats=v,thereisanedge(v,s),andtherearenoedgesoftheform(s,v).
GiveanO(N)algorithmtodeterminewhetherornotGhasasink,assumingthat
9.43 Whenavertexanditsincidentedgesareremovedfromatree,acollectionofsub-
treesremains.Givealinear-timealgorithmthatﬁndsavertexwhoseremovalfrom
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
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.
Pisspeciﬁedasaparametertothealgorithm.(Ifthepenaltyis0,thentheproblem
istrivial.)Describeanalgorithmtosolvethisversionoftheproblem.Whatisthe
runningtimeforyouralgorithm?
9.48 Supposethatthemazemayormaynothaveasolution.
a. Describealinear-timealgorithmthatdeterminestheminimumnumberofwalls
queue.)
b.Describeanalgorithm(notnecessarilylinear-time)thatﬁndsashortestpath
afterknockingdowntheminimumnumberofwalls.Notethatthesolutionto
knockdown.(Hint:UseExercise9.47.)
9.49 Writeaprogram to computeword d ladders wheresingle-charactersubstitutions
speciﬁedbytheuser.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,eitherﬁndaproof(ifoneexists)thatXisbetter
thanY,orindicatethatnoproofofthisformcanbefound.
9.51 Theinputisacollectionofcurrenciesandtheirexchangerates.Isthereasequence
ofexchangesthatmakesmoneyinstantly?Forinstance,ifthecurrenciesareX,Y,
andZandtheexchangerateis1Xequals2Ys,1Yequals2Zs,and1Xequals3
haveprerequisitesthatmustbefollowed.Assumethatallcoursesareofferedevery
semesterandthatthestudentcantakeanunlimitednumberofcourses.Givenalist
ofcoursesandtheirprerequisites,computeaschedulethatrequirestheminimum
numberofsemesters.
instance,TomHankshasaBaconnumberof1;hewasinApollo13 withKevin
Bacon.SallyFieldshasaBaconnumberof2,becauseshewasinForrestGumpwith
TomHanks,whowasinApollo13withKevinBacon.Almostallwell-knownactors
haveaBaconnumberof1or2.Assumethatyouhaveacomprehensivelistof
actors,withroles,3anddothefollowing:
a. Explainhowtoﬁndanactor’sBaconnumber.
b.ExplainhowtoﬁndtheactorwiththehighestBaconnumber.
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,seetheInternetMovieDatabaseﬁles:
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
includingthemorecarefulattentiontorunningtimes,arecoveredin[41],[44],and[51].
[31],asdescribedin[36].Dijkstra’salgorithmappearedin[10].Theimprovementsusing
d-heapsandFibonacciheapsaredescribedin[30]and[16],respectively.Theshortest-path
algorithmwithnegativeedgeweightsisduetoBellman[3];Tarjan[51]describesamore
efﬁcientwaytoguaranteetermination.
FordandFulkerson’sseminalworkonnetworkﬂowis[15].Theideaofaugmenting
approachestotheproblemcanbefoundin[11],[34],[23],[7],[35],[22],and[43].An
algorithmforthemin-costﬂowproblemcanbefoundin[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].Theﬁrstlinear-timestrongcomponents
algorithm(Exercise9.28)appearsinthesamepaper.Thealgorithmpresentedinthetext
isduetoKosaraju(unpublished)andSharir[46].Otherapplicationsofdepth-ﬁrstsearch
appearin[27],[28],[48],and[49](asmentionedinChapter8,theresultsin[48]and
[49]havebeenimproved,butthebasicalgorithmisunchanged).
materialcanbefoundin[1].TheNP-completenessofsatisﬁabilityisshownin[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
Efﬁcient solutions for theunweighted matching problem for generalgraphsarequite
complex.Detailscanbefoundin[12],[17],and[19].
Exercise9.35dealswith planargraphs,whichcommonly arise in practice.Planar
graphsareverysparse,andmanydifﬁcultproblemsareeasieronplanargraphs.Anexam-
pleisthegraphisomorphismproblem,whichissolvableinlineartimeforplanargraphs
[29].Nopolynomialtimealgorithmisknownforgeneralgraphs.
1.A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,TheDesignandAnalysisofComputerAlgorithms,
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
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 Efﬁciency 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
434–443.
18.H.N.Gabow,Z.Galil,T.H.Spencer,andR.E.Tarjan,“EfﬁcientAlgorithmsforFinding
MinimumSpanningTreesonDirectedandUndirectedGraphs,”Combinatorica,6(1986),
109–122.
19.Z.Galil,“EfﬁcientAlgorithmsforFindingMaximumMatchingsinGraphs,”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.
25.J.E.HopcroftandR.M.Karp,“Ann5/2 AlgorithmforMaximumMatchingsinBipartite
Graphs,”SIAMJournalonComputing,2(1973),225–231.
26.J.E.HopcroftandR.E.Tarjan,“Algorithm447:EfﬁcientAlgorithmsforGraphManipu-
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,“EfﬁcientPlanarityTesting,”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,“EfﬁcientAlgorithmsforShortestPathsinSparseNetworks,”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,“DeterminingtheMaximalFlowinaNetworkbytheMethodofPreﬂows,”
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.,
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-ﬁfthAnnualACM
SymposiumonTheoryofComputing(2013).
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
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,wehavebeenconcernedwiththeefﬁcientimplementationofalgorithms.Wehave
seenthatwhenanalgorithmisgiven,theactualdatastructuresneednotbespeciﬁed.It
isuptotheprogrammertochoosetheappropriatedatastructureinordertomakethe
runningtimeassmallaspossible.
Inthischapter,weswitchourattentionfromtheimplementationofalgorithmstothe
designofalgorithms.Mostofthealgorithmsthatwehaveseensofararestraightforwardand
simple.Chapter9containssomealgorithmsthataremuchmoresubtle,andsomerequire
anargument(insomecaseslengthy)toshowthattheyareindeedcorrect.Inthischapter,
wewillfocusonﬁveofthecommontypesofalgorithmsusedtosolveproblems.Formany
problems,itisquitelikelythatatleastoneofthesemethodswillwork.Speciﬁcally,for
eachtypeofalgorithmwewill...
Seethegeneralapproach.
Lookatseveralexamples(theexercisesattheendofthechapterprovidemanymore
examples).
Discuss,ingeneralterms,thetimeandspacecomplexity,whereappropriate.
10.1 GreedyAlgorithms
threegreedyalgorithmsinChapter9:Dijkstra’s,Prim’s,andKruskal’salgorithms.Greedy
withoutregardforfutureconsequences.Generally,thismeansthatsomelocaloptimumis
chosen.This“takewhatyoucangetnow”strategyisthesourceofthenameforthisclassof
algorithms.Whenthealgorithmterminates,wehopethatthelocaloptimumisequaltothe
globaloptimum.Ifthisisthecase,thenthealgorithmiscorrect;otherwise,thealgorithmhas
Thereareseveralreal-lifeexamplesofgreedyalgorithms.Themostobviousisthecoin-
changingproblem.TomakechangeinU.S.currency,werepeatedlydispensethelargest
449
450
Chapter10 AlgorithmDesignTechniques
denomination.Thus,togiveoutseventeendollarsandsixty-onecentsinchange,wegive
outaten-dollarbill,aﬁve-dollarbill,twoone-dollarbills,twoquarters,onedime,and
onepenny.Bydoingthis,weareguaranteedtominimizethenumberofbillsandcoins.
Thisalgorithmdoesnotworkinallmonetarysystems,butfortunately,wecanprovethatit
doesworkintheAmericanmonetarysystem.Indeed,itworkseveniftwo-dollarbillsand
ﬁfty-centpiecesareallowed.
Trafﬁcproblemsprovideanexamplewheremakinglocallyoptimalchoicesdoesnot
alwayswork.Forexample,duringcertainrushhourtimesinMiami,itisbesttostayoff
theprimestreetseveniftheylookempty,becausetrafﬁcwillcometoastandstillamile
makeatemporarydetourinthedirectionoppositeyourdestinationinordertoavoidall
trafﬁcbottlenecks.
Intheremainderofthissection,wewilllookatseveralapplicationsthatusegreedy
algorithms.Theﬁrst applicationisasimpleschedulingproblem.Virtually allschedul-
ingproblemsareeitherNP-complete(orofsimilardifﬁcultcomplexity)oraresolvable
byagreedyalgorithm.Thesecondapplicationdealswithﬁlecompressionandisoneof
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
ﬁnishesin15
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.3isarrangedbyshortestjobﬁrst.Wecanshowthat
thiswillalwaysyieldanoptimalschedule.Letthejobsintheschedulebej
i
1
,j
i
2
,...,j
i
N
.
Theﬁrstjobﬁnishesintimet
i
1
.Thesecondjobﬁnishesaftert
i
1
+t
i
2
,andthethirdjob
ﬁnishesaftert
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),theﬁrstsumisindependentofthejobordering,so
onlythesecondsumaffectsthetotalcost.Supposethatinanorderingthereexistssome
x>ysuchthatt
i
x
<t
i
y
.Thenacalculationshowsthatbyswappingj
i
x
andj
i
y
,thesecond
sumincreases,decreasingthetotalcost.Thus,anyscheduleofjobsinwhichthetimesare
notmonotonicallynondecreasingmustbesuboptimal.Theonlyschedulesleftarethosein
whichthejobsarearrangedbysmallestrunningtimeﬁrst,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
ﬁrst.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