算法导论第一次作业答案

CSCE629Homework1Name:TianJinUIN:5240058771.(1)Textbookpage370,Exercise15.1-2:Show,bymeansofacoun-terexample,thatthefollowing\greedystrategydoesnotalwaysdetermineanoptimalwaytocutrods.Denethedensityofarodoflengthitobepi=i,thatis,itsvalueperinch.Thegreedystrategyforarodoflengthncutsoarstpieceoflengthi,where1in,havingmaximumdensity.Itthencontinuesbyapplyingthegreedystrategytotheremainingpieceoflengthni.Solution:First,let'sanalyzethisrodcutproblemingeneral:Input:1.arodeoflengthn(aninteger)2.fori=1;2;:::;n,arodoflengthihasapricepi3.densityofarodoflengthiispi=iOutput:howtocuttherodsothatthetotalpriceismaximum.Ifwedenedkastheleft-mostcut,thentherodcuttingproblemhasarecursivefunctionrn=maxk=1;


;nfpk+rnkgIamnowgivingacounterexampleforthegreedystrategy.Assumingthatthepriceanddensitylistedasfollowingtable:lengthi12345pricepi114243640densitypi=i17898Setthegivenlengthas5.Ifweusethegreedystrategy,werstchoosetocuttherodatthelengthof4becausethedensityoflength4ismaximum,whichis9.Thenwewillget2parts:length4andlength1.Thetotalpriceofthisconditionis36+1=37.However,thebestwaytocuttherodiscuttingtherodtohavetwoparts:length2andlength3,whichhasamaximumprice14+24=38.Soitseemsthatthe\greedystrategydoesnotalwaysdetermineanoptimalwaytocutrods.2.(2)Textbookpage408,Problem15-7:ViterbialgorithmWecanusedynamicprogrammingonadirectedgraphG=(V;E)forspeechrecognition.Eachedge(u;v)2Eislabeledwithasound(u;v)fromanitesetofsounds.Thelabeledgraphisaformalmodelofapersonspeakingarestrictedlanguage.Eachpathinthegraphstartingfromadistinguishedvertexv02Vcorrespondstoapossiblesequenceofsoundsproducedbythemodel.Wedenethelabelofadirectedpathtobetheconcatenationofthelabelsoftheedgesonthatpath.a.Describeanecientalgorithmthat,givenanedge-labeledgraphGwithdistinguishedvertexv0andasequences=h1;2;:::;kiofsoundsfrom,returnsapathinGthatbeginsatv0andhassasitslabel,ifanysuchpath1exists.Otherwise,thealgorithmshouldreturnNO-SUCH-PATH.Analyzetherunningtimeofyouralgorithm.(Hint:YoumayndconceptsfromChapter22useful.)Now,supposethateveryedge(u;v)2Ehasanassociatednonnegativeprobabilityp(u;v)oftraversingtheedge(u;v)fromvertexuandthusproducingthecorrespondingsound.Thesumoftheprobabilitiesoftheedgesleavinganyvertexequals1.Theprobabilityofapathisdenedtobetheproductoftheprobabilitiesofitsedges.Wecanviewtheprobabilityofapathbeginningatv0astheprobabilitythata\randomwalkbeginningatv0willfollowthespeciedpath,wherewerandomlychoosewhichedgetotakeleavingavertexuaccordingtotheprobabilitiesoftheavailableedgesleavingu.b.Extendyouranswertopart(a)sothatifapathisreturned,itisamostprobablepathstartingatv0andhavinglabels.Analyzetherunningtimeofyouralgorithm.Solution(a):Inordertounderstandclearly,werstlyneedtogureouttheinputandtheoutput.Weneedtousedynamicprogrammingtosolvethisproblem:Input:agraphG(V;E)whichcontainsfollowingelements:1.vertexv02.astringscomposedofsomecharactersinalphabet.Output:ndwhetherthereisapathfromv0labeledwiths.Forexample,if=fa;b;c;d;e;f;gg,v0=1ands=ecf.ConsiderthegivenpathIcreatedmyself(SeeFigure1)andithasapathf1;5;4;3glabeledwiths.Figure1:ThegivengraphGFromtheChapter22,wecanlearnthatintheexpressionofG(V;E),the\Vdenotestheverticesand\Erepresentsalltheedges.PartI.MyIdea:1.state:IdeneastateasisaPath(i;x)whichmeansthatstartingfromthevertexv0,whetherithasapathtovertexxthroughalltheedgess=2h1;2;:::;ii.(isaPath(i;x)=true;ifthereisapathsatisfiedisaPath(i;x)=false;ifthereisnopathsatisfied(1)2.initialize:ItisobviousthatisaPath(0,v0)=true,andfor(x6=v0),isaPath(0;v)=false.3.function:(isaPath(i;x)=isaPath(i1;y);ifE(y;x)=iisaPath(i;x)=false;otherwise(2)whereE(y;x)denotesthattheedgevaluebetweenvertexxandvertexy.4.result:accordingtothequestion,weneedtocheckisaPath(k;v)astheresult.Aftertracingback,wecanknowwhattheexactpath.PartII.Presentalgorithminpseudocode:ISAPATH(i;x)1ifi=0,2returntrue;3elseforx6=v04ISAPATH(0;v)=false5for0ik6ifE(y;x)=i7ISAPATH(i;x)=ISAPATH(i1;y)8elseISAPATH=false9returnISAPATH(k;v)PartIII.ProvecorrectnessLookingbackattheexampleIgave:Initially,itisobviousthatisaPath(0,1)=true;Thenwecanstarttocalcu-latethefollowingvalue:BecauseE(1,5)=e,thenisaPath(1,5)=isaPath(0,1)=true;BecauseE(5,4)=c,thenisaPath(2,4)=isaPath(1,5)=true;BecauseE(4,3)=f,thenisaPath(3,3)=isaPath(2,4)=true;Finally,wegettheresultisaPath(3,3).Aftertracingback,wecanknowtheexactpathisf1;5;4;3g.PartIV.TimecomplexityIthinktherunningtimeisO((n+jEj)k),wherenisthenumberofvertices,jEjisthetotalnumberofedges,kistheindexofthestrings.Solution(b):Theideaisthesameasproblem(a).Theonlydierenceistherecursivefunctionhastochangealittle:38:isaPath(i;x)=maxE(y;x)=iisaPath(i1;y)p(y;x)ifE(y;x)=iisaPath(i;x)=false;otherwise(3)BecauseIonlyneedtocomparewiththevaluenexttoitself,thenIthinkthetimecomplexityisO((n+jEj)k).4