资源描述:
《算法导论第一次作业答案.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、CSCE629Homework1Name:TianJinUIN:5240058771.(1)Textbookpage370,Exercise15.1-2:Show,bymeansofacoun-terexample,thatthefollowinggreedy"strategydoesnotalwaysdetermineanoptimalwaytocutrods.Denethedensityofarodoflengthitobepi=i,thatis,itsvalueperinch.Thegreedystrategyforarodoflengthncutso
2、arstpieceoflengthi,where1in,havingmaximumdensity.Itthencontinuesbyapplyingthegreedystrategytotheremainingpieceoflengthn i.Solution:First,let'sanalyzethisrodcutproblemingeneral:Input:1.arodeoflengthn(aninteger)2.fori=1;2;:::;n,arodoflengthihasapricepi3.densityofarodoflengthiispi=iOu
3、tput:howtocuttherodsothatthetotalpriceismaximum.Ifwedenedkastheleft-mostcut,thentherodcuttingproblemhasarecursivefunctionrn=maxfpk+rn kgk=1;;nIamnowgivingacounterexampleforthe"greedy"strategy.Assumingthatthepriceanddensitylistedasfollowingtable:lengthi12345pricepi114243640densityp
4、i=i17898Setthegivenlengthas5.Ifweusethegreedystrategy,werstchoosetocuttherodatthelengthof4becausethedensityoflength4ismaximum,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)fromanitesetof
6、sounds.Thelabeledgraphisaformalmodelofapersonspeakingarestrictedlanguage.Eachpathinthegraphstartingfromadistinguishedvertexv02Vcorrespondstoapossiblesequenceofsoundsproducedbythemodel.Wedenethelabelofadirectedpathtobetheconcatenationofthelabelsoftheedgesonthatpath.a.Describeanecient
7、algorithmthat,givenanedge-labeledgraphGwithdistinguishedvertexv0andasequences=h1;2;:::;kiofsoundsfrom,returnsapathinGthatbeginsatv0andhassasitslabel,ifanysuchpath1exists.Otherwise,thealgorithmshouldreturnNO-SUCH-PATH.Analyzetherunningtimeofyouralgorithm.(Hint:Youmayndconceptsfrom
8、Chapt