算法导论15-16-答案

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,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-chainproductwhosesequenceofdimensionsis5,10,3,12,5,50,6.Solution:Solvethematrixchainorderforaspecificproblem.ThiscanbedonebycomputingMATRIX-CHAIN-ORDER(p)wherep=5,10,3,12,5,50,6orsimplyusingtheequation:+++==−≤.if}],1[],{min[min,if0],[1jipppjkmkijijimjkijkiThetableiscomputedsimplybythefactthatm[i,i]=0foralli.Thisinformationisusedtocomputem[i,i+1]fori=1,…,n–1ansoon.Theresultingtableisthefollowing: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=4s[1,5]=4,s[2,6]=2s[1,6]=2Finally,wehave(A1A2)((A3A4)(A5A6)).15.4-1(5-9)DetermineanLCSof1,0,0,1,0,1,0,1and0,1,0,1,1,0,1,1,0.Solution:yj010110110xi000000000010↑01←111←111←1001↑12←2←22←2←22001↑12↑2↑23←3←3310↑12↑233↑344←4001↑23↑3↑34↑4↑4510↑12↑344↑455↑5001↑23↑4↑45↑5↑5610↑12↑345↑666↑6Alongestcommonsequencecouldbe1,0,0,1,1,0asillustratedbelow(therecouldbesomeotherLCS’,ifwechoose←insteadof↑whenc[i–1,j]=c[i,j–1]):X:–,1,0,–,–,0,1,0,1,0,1Y:0,1,0,1,1,0,1,–,1,0,–SotheLCSis100110.15.5-3(5-15)Supposethatinsteadofmaintainingthetablew[i,j]wecomputedthevalueofw[i,j]directlyfromequation(5-5)inline8ofOPTIMAL-BSTandusethiscomputedvalueinline10.HowwouldthischangeaffecttheasymptoticrunningtimeofOPTIMAL-BST?∑∑−==+=jilljillqpjiw1),((5-5)OPTIMAL-BST(p,q,n)1fori←1ton+12doe[i,i-1]←qi-13w[i,i-1]←qi-14forl←1ton5dofori←1ton–l+16doj←i+l–17e[i,j]←∞8w[i,j]←w[i,j–1]+pj+qj9forr←itoj10dot←e[i,r–1]+e[r+1,j]+w[i,j]11ifte[i,j]12thene[i,j]←t13root[i,j]←r14returneandrootSolution:Actually,itwouldnotchangetheasymptoticrunningtimeatall.Tocomputew[i,j]manuallyonline8wouldrequireΘ(j–i)additions,insteadofΘ(1)asinthebook’sversion.However,line9doesnotaloopfromitojanyway,whichtakesΘ(j–i)time.DoinganotherΘ(j–i)workonline8wouldnotaffecttheasymptoticrunningtimeofΘ(n3).15-4(5-19)Planningacompanyparty.ProfessorStewartisconsultingforthepresidentofacorporationthatisplanningacompanyparty.Thecompanyhasahierarchicalstructure;thatis,thesupervisorrelationformstreerootedatthepresident.Thepersonalofficehasrankedeachemployeewithaconvivialityrating,whichisarealnumber.Inordertomakethepartyfunforallattendees,thepresidentdoesnotwantbothanemployeeandhisorherimmediatesupervisortoattend.ProfessorStewartisgiventhetreethatdescribesthestructureofthecorporation,usingtheleft-child,right-siblingrepresentationdescribedinSection10.4(CLRS).Eachnodeofthetreeholdsinadditiontopointers,thenameofanemployeeandthatemployee’sconvivialityranking.Describeanalgorithmtomakeupaguestlistthatmaximizesthesumoftheconvivialityratingoftheguests.Analyzetherunningtimeofyouralgorithm.Solution:Thisproblemmaybesolvedinlineartimeusingdynamicprogramming.Letc[x]denotetheconvivialityofemployeex.WewishtoselectasubsetofemployeesSmaximizing∑x∈Sc[x],suchthatifx∈S,thenparent[x]∉S.Inordertousedynamicprogramming,wemustbeabletocomputetheoptimalsolutionofourproblemintermsofoptimalsolutionstosmallersubproblemsofthesameform.Theseoptimalsolutionstosubproblemswillbethefollowing:letM(x)denotethemaximumpossibleconvivialitysumifoneweretoinviteonlyemployeesfromthesubtreerootedatemployeex,suchthatxisinvited.SimilarlyletM’(x)denotethemaximumconvivialitysumforx’ssubtreeifxisnotinvited.WecanexpressM(x)andM’(x)recursivelyintermsofoptimalsolutionsto“smaller”subproblemsasfollows:M(x)=c[x]+∑y:parent[y]=xM’(y)M’(x)=∑y:parent[y]=xmax{M(y),M’(y)}Thefirstequationstatesthattheoptimalwaytoselectemployees(includingx)fromx’ssubtreeistooptimallyselectemployeesfromthesubtreeofeachchildyofxsuchthatyisnotinvited.Thesecondequationexpressesthefactthattheoptimalwaytoselectemployees(notincludingx)fromx’ssubtreeistooptimallyselectemployeesfromsubtreesofchildrenyofx,whereitisofnoconsequencewhetherornotyisselected.ThefollowingpseudocodeshowhowwecancomputeM(x)andM’(x)foreveryemployeexusingasinglerecursivetransversalofthecompanytreeinO(n)time:SOLVE(x)1M(x)←c[x]2M’(x)←03y←left-child[x]4whiley≠NIL5doSOLVE(y)6M(x)←M(x)+M’(y)7M’(x)←M’(x)+max{M(y),M’(y)}8y←right-sibling[y]ThealgorithmwillbestartedbycallingSOLVE(p),wherepdenotesthecompanypresident.Uponterminationtheoptimalconvivialitysumfortheentirecompanywillbegivenbymax{M(p),M’(p)}.Howdoesonedeterminethesetofemployeestoinvitethatachievesthismaximumconvivialitysum?ThismaybedoneinO(n)timewithanothertreetransversal,bycallingINVITE(p),illustratedbythefollowingpseudocode:INVITE(x)1ifM(x)M’(x)2thenInvitextotheparty3forallgrandchildrenyofx4INVITE(y)5elseforallchildrenyofx