算法导论第一次作业答案.pdf

《算法导论第一次作业答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CSCE629Homework1Name:TianJinUIN:5240058771.(1)Textbookpage370,Exercise15.1-2:Show,bymeansofacoun-terexample,thatthefollowinggreedy"strategydoesnotalwaysdetermineanoptimalwaytocutrods.Denethedensityofarodoflengthitobepi=i,thatis,itsvalueperinch.Thegreedystrategyforarodoflengthncutso

2、arstpieceoflengthi,where1in,havingmaximumdensity.Itthencontinuesbyapplyingthegreedystrategytotheremainingpieceoflengthni.Solution:First,let'sanalyzethisrodcutproblemingeneral:Input:1.arodeoflengthn(aninteger)2.fori=1;2;:::;n,arodoflengthihasapricepi3.densityofarodoflengthiispi=iOu

3、tput:howtocuttherodsothatthetotalpriceismaximum.Ifwedenedkastheleft-mostcut,thentherodcuttingproblemhasarecursivefunctionrn=maxfpk+rnkgk=1;


;nIamnowgivingacounterexampleforthe"greedy"strategy.Assumingthatthepriceanddensitylistedasfollowingtable:lengthi12345pricepi114243640densityp

4、i=i17898Setthegivenlengthas5.Ifweusethegreedystrategy,werstchoosetocuttherodatthelengthof4becausethedensityoflength4ismaximum,whichis9.Thenwewillget2parts:length4andlength1.Thetotalpriceofthisconditionis36+1=37.However,thebestwaytocuttherodiscuttingtherodtohavetwoparts:length2andleng

5、th3,whichhasamaximumprice14+24=38.Soitseemsthatthegreedy"strategydoesnotalwaysdetermineanoptimalwaytocutrods.2.(2)Textbookpage408,Problem15-7:ViterbialgorithmWecanusedynamicprogrammingonadirectedgraphG=(V;E)forspeechrecognition.Eachedge(u;v)2Eislabeledwithasound(u;v)fromanitesetof

6、sounds.Thelabeledgraphisaformalmodelofapersonspeakingarestrictedlanguage.Eachpathinthegraphstartingfromadistinguishedvertexv02Vcorrespondstoapossiblesequenceofsoundsproducedbythemodel.Wedenethelabelofadirectedpathtobetheconcatenationofthelabelsoftheedgesonthatpath.a.Describeanecient

7、algorithmthat,givenanedge-labeledgraphGwithdistinguishedvertexv0andasequences=h1;2;:::;kiofsoundsfrom,returnsapathinGthatbeginsatv0andhassasitslabel,ifanysuchpath1exists.Otherwise,thealgorithmshouldreturnNO-SUCH-PATH.Analyzetherunningtimeofyouralgorithm.(Hint:Youmayndconceptsfrom

8、Chapt