算法作业

算法设计与分析课后作业elie*2012年2月16*[e-mail]11小试身手——第一次作业1.1TrueorFalse?Trueorfalse?ConsideraninstanceoftheStableMatchingProbleminwhichthereexitsamanmandawomanwsuchthatmisrankedfirstonthepreferencelistofwandwisrankedfirstonthepreferencelistofm.ThenineverystablematchingSforthisinstance,thepair(m;w)belongstoS.命题为真。用反证法证明。假设存在稳定匹配S，(m;w)2S.那么存在一名“女性”w′和一名“男性”m′,使得(m;w′)2S;(m′;w)2S.又因为对于m,他更喜欢w而非w′,对于w,她更喜欢m而非m′,从而S是不稳定的。因此与假设S是稳定的矛盾。从而对做任意的一个稳定的匹配S,(m;w)2S.1.2TrueorFalse?Trueorfalse?InthestablematchingSgeneratedbyG-Salgorithm,eachwomanispairedwithherworstvalidpartner.命题为真。设w1的worstvalidpartner是m1.假设G-S算法产生的稳定匹配使w1不与m1相配。不妨设w1与m2相配。那么w1更喜欢m2而非m1（因为m1是w1的wosrtvalidpatner）。设另一匹配S中w1与m1相配。m2与w2相配。在S中m2的配偶w1是m2的bestvalidpatner.故m2更喜欢w1而非w2,又w1更喜欢m2而非m1.从而w1m2不稳定。1.3TrueorFalseSupposewehavetwotelevisionstations,AandB.Therearenprime-timeprogrammingslots,andeachstationhasnTVshows.Eachstationwantstoassigneachshowtoadistinctslotsoastoattractasmuchmarketshareaspossible.Hereisthewaywedeterminehowwellthetwostationsperformrelativetoeachother,giventheirschedules.Eachshowhasafixedscore.We’llassumethatnotwoshowshaveexactlythesamescore.Astationwinsagiventimeslotiftheshowthatitschedulesforthetimeslothasahigherscorethantheshowtheotherstationschedulesforthattimeslot.Thegoalofeachstationistowinasmanytimeslotsaspossible.SupposeStationArevealsascheduleSandStationBrevealsascheduleT.We’llsaythatthepairofschedule(S;T)isstableifneitherstationcanunilaterallychangeitsownscheduleandwinmoretimeslots.Thatis,thereisnoscheduleS′suchthatStationAwinsmoreslotswiththepair(S′;T)thanitdidwiththepair(S;T);andsymmetrically,thereisnoscheduleT′suchthatStationBwinsmoreslotswiththepair(S;T).Decidewhetheryou2thinkthefollowingstatementistrueorfalse.Ifitistrue,giveanalgorithm.Ifitisfalse,giveacounterexample.Trueorfalse?ForeverysetofTVshowsandscores,thereisalwaysastablepairofschedules.命题为假。考n=2的情形，设A的两个节目的分数分别为a1;a2,B的两个节目的分数分别为b1;b2,并且a1b1a2b2.以这样的分数，无论怎么样的计划，两公司总可以单方面地改变计划以获得更多的播放机会。例如，a1;b1竞争第一个节目时间，a2;b2竞争第二个节目时间，这样的计划B公司获得零个播出时间。但是B公司可以改变策略，让b1与a2竞争第二个节目，b2与a1竞争第一个节目，这样，B公司可以获得一个播出时间。同样，a1与b2竞争，a2与b1竞争时，A以改变策略获得更多的播出时间。1.4StableMatchingPSLisashippingcompanythatownsnshipsandprovideservicetonports.Eachshiphasaschedulethatsays,foreachdayinsomem(mn)dayperiod,whethertheshipisatseaorstayingatoneport.Duringtheperiod,eachshipvisitseachportonce,andeachvisitlastsexactlyoneday.Forsafetyreasons,PSLhasthefollowingstrictrequirement:(y)Notwoshipscanbeinthesameportonthesameday.Thecompanywantstoperformmaintenanceonalltheshipsinthefollowingmdayperiod.Inthiscase,eachshipSiwillarriveinonescheduledportandsimplyremainstherefortherestoftheperiod,ignoringtherestofitsschedule.Nowthequestionis:Giventhescheduleforeachship,findwheneachshipshouldstopitstravelsothatcondition(y)continuestohold.Trytogiveanalgorithmtofindthesolution.此问题类似于稳定婚姻问题。只需将船类比成稳定婚姻问题中的男士，码头类比成女士，然后套用G-S算法。1.5ComplexityAnalysisDesignadatastructuretosupportthefollowingtwooperationsforasetSofintegers:Insert(S,x)insertsxintosetS;Delete-Larger-Half(S)deletesthelargest⌊S=2⌋elementsfromS.ExplainhowtoimplementthisdatastructuresothatanysequenceofmoperationsrunsinO(m)time.将数据结构设计为一个动态数组S.1.Insert（插入操作）每次向数组插入一个元素。当数组存满时，若执行插入操作，则另外申请加倍的内存空间，并将原空间的数据拷贝到新申请的空间中，删除原内存空间。32.Delete-Larger-Half（删除操作）忽略对删除操作前数据为空的判断时间。每次删除操作分两步：•获取数组中所有元素的中位数（可以采用《算法导论》（第二版）9.3节最坏情况线性时间获取线性表中位数的算法）。•删除数组中最大的⌊S=2⌋个元素，只需扫描整个数组，如果扫描过程中当前元素小于中位数，则添加到数组的前半部分。如果当前元素大于或等于中位数，则删除这个元素。可以用平摊分析法，得出任何次序的插入和删除操作的时间复杂度是O(n).1.6ComplexityAnalysisInstockmarket,HH-index(historicallyhighest)ofthecurrentpriceiskmeansthatcur-rentpriceisthehighestpriceinthepreviouskdays,butnotthehighestoneinthepreviousk+1days.Forexample,thepricechangesasshowedinthefollowingfigure.2345678123456HH+++++++ThepriceinDay5isthehighestinDays5;4;3;2,butnothighestoneinDays5;4;3;2;1,thusHH(5)=4;ThepriceinDay4isthehighestinDays4;3;2,butnothighestoneinDays4;3;2;1,thusHH(4)=3;ThepriceinDay3isthehighestinDay3,butnothighestoneinDays3;2,thusHH(3)=1;Theinputinthisexampleis8;4;3;5;6;2,theansweris1;1;1;3;4;1.4Giventhepricesofndays,pleasegiveanalgorithmofO(n)timecomplexitytocalculatetheHH-indexofalldays.解：只简单地给出算法(算法分析是简单的——时间复杂度O(n))：while还有没处理的数据do将下降序列插入到队列Q中。将上升序列插入到栈S中。k1=jSj;k2=jQj;whileS̸=∅dot=s:pop();HH[t]=k;whileQ̸=∅andv[Q:top()]v[t]dotq=Q:pop();HH[ta]=1;endwhileHH[t]+=jQj+1;endwhilewhileQ̸=∅dotq=Q:pop();HH[tq]=1;endwhileendwhile52NP完全问题的证明2.1NP-completenessThesubgraph-isomorphismproblemtakestwographsG1andG2andaskswhetherG1isisomorphictoasubgraphofG2.Showthatthesubgragh-isomorphismproblemisNP-complete.Proof.FirstweprovethattheSubgraphIsomorphismproblemisinNP.Thecertificateis(G1=(V1;E1);G2=(V2;E2);φV1!V2).Theverifyingalgorithmchecksifφisaone-to-onefunction,andforallu;v2V1whether(u;v)2E1ifandonlyif(φ(u);φ(v))2E2.Secondly,weprovethatCIQUEPSubgraghIsomorphism.Let(G=(V;E);k)beaninputinstanceforCLIQUE.DefineG1tobethecompletegraphonkvertices,andG2tobethegrapghG.Then(G1;G2)2SubgraghIsomorphismifandonlyif(G;k)2CLIQUE.2.2NP-completenessGivenanintegermnmatrixAandanintegerm-vectorb,the0-1IntegerProg