算法导论15-16 答案

《算法导论15-16 答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安电子科技大学计算机学院霍红卫SolutionstoChapters15&1615.1-1(5-1)ShowhowtomodifythePRINT-STATIONSproceduregivenbelowtoprintoutthesituationsinincreasingorderofstationnumber.PRINT-STATIONS(l,n)1i←l*2print“line”i“,station”n3forj←ndownto24doi←li[j]5print“line”i“,station”j–1Solution:RECURSIVE-PRINT-STATIONS(l,i,

2、j)1ifj=0thenreturn2RECURSIVE-PRINT-STATIONS(l,li[j],j–1)3print“line”i“,station”jToprintoutallthestations,callPRINT-STATIONS(l,l*,n)15.2-1(5-5)Findanoptimalparenthesizationofamatrix-chainproductwhosesequenceofdimensionsis<5,10,3,12,5,50,6>.Solution:Solvethematrixchainorderforaspecificproblem.Th

3、iscanbedonebycomputingMATRIX-CHAIN-ORDER(p)wherep=<5,10,3,12,5,50,6>orsimplyusingtheequation:0ifi=j,m[i,j]=min{min[i,k]+m[k+1,j]+ppp}ifi

4、Them-table:m[1,2]=150,m[2,3]=360,m[3,4]=180,m[4,5]=3000,m[5,6]=1500m[1,3]=330,m[2,4]=330,m[3,5]=930,m[4,6]=1860m[1,4]=405,m[2,5]=2430,m[3,6]=1770m[1,5]=1655,m[2,6]=1950m[1,6]=2010Thes-table:s[1,2]=1,s[2,3]=2,s[3,4]=3,s[4,5]=4,s[5,6]=5s[1,3]=2,s[2,4]=2,s[3,5]=4,s[4,6]=4s[1,4]=2,s[2,5]=2,s[3,6=4

5、s[1,5]=4,s[2,6]=2s[1,6]=2Finally,wehave(A1A2)((A3A4)(A5A6)).15.4-1(5-9)DetermineanLCSof<1,0,0,1,0,1,0,1>and<0,1,0,1,1,0,1,1,0>.Solution:yj010110110xi000000000010↑01↖←1↖↖11←1↖↖11←1001↖↑1↖2←2←2↖2←2←2↖2001↖↑1↖2↑2↑2↖3←3←3↖310↑12↖↑2↖3↖3↑3↖↖44←4001↖↑2↖3↑3↑3↖4↑4↑4↖510↑12↖↑3↖↖44↑4↖↖55↑5001↖↑2↖3↑4↑4↖5↑

6、5↑5↖610↑12↖↑3↖↖45↑6↖↖66↑6Alongestcommonsequencecouldbe<1,0,0,1,1,0>asillustratedbelow(therecouldbesomeotherLCS’,ifwechoose←insteadof↑whenc[i–1,j]=c[i,j–1]):X:<–,1,0,–,–,0,1,0,1,0,1>Y:<0,1,0,1,1,0,1,–,1,0,–>SotheLCSis100110.15.5-3(5-15)Supposethatinsteadofmaintainingthetablew[i,j]wecomputedthev

7、alueofw[i,j]directlyfromequation(5-5)inline8ofOPTIMAL-BSTandusethiscomputedvalueinline10.HowwouldthischangeaffecttheasymptoticrunningtimeofOPTIMAL-BST?jjw(i,j)=∑pl+∑ql(5-5)l=il=i−1OPTIMAL-BST(p,q,n)1fori←1ton+12doe[i,i-1]←qi-13w[i,i-1]←