=========================preview======================
(COMP271)2002Spring_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
COMP271DesignandAnalysisofAlgorithms 2002SpringSemester{CunshengDing SampleSolutionstotheMidtermExam
Problem1:SupposeT1(n).O(f(n))andT2(n).O(f(n)).Whichofthefollowingaretrue. Justwritedownyouranswerwithoutgivinganyjusti.cation. (a)T1(n)+T2(n).O(f(n)) T 1(n)
(b).O(1)
T 2(n)
(c)T1(n).O(T2(n))
Solution:(a)
Problem2:AlocalminimumofanarrayA[a::b]isanelementA[k]satisfyingA[k;1]. A[k].A[k+1].Weassumethata.b;2,A[a].A[a+1]andA[b;1].A[b].these conditionsguaranteethatalocalminimummustexist.Designanalgorithmfor.ndingalocal minimumofthearrayA[a::b]whichissubstantiallyfasterthantheobviousliner-timeO(b;a) one,intheworstcase.Justifythecorrectnessofyouralgorithmandanalyzeitsrunningtime. Solution:DividethearrayA[a::b]intotwosubarraysA[a::c]andandA[c+1::b],wherec. b(a+b).2c.Therearethreecases:
1.A[c;1].A[c].A[c+1]:Inthiscase,cisalocalminimum.
2.A[c;1].A[c].A[c+1]:Inthiscase,A[c::b]musthavealocalminimum.
3.A[c;1].A[c].A[c+1]:Inthiscase,A[a::c]musthavealocalminimum.
Theaboveanalysissuggeststhefollowingdivide-and-conqueralgorithm.
LocalMinimun(A,a,b){ ifb-a.2,outputa+1. else{
c.[(a+b)/2].
ifA[c-1]\geqA[c]\leqA[c+1].outputc.
else{

ifA[c-1]\geqA[c]\geqA[c+1].LocalMinimun(A,c,b). else{ LocalMinimun(A,a,c). } } } }
LetT(n)denotetherunningtimeofthisalgorithmforthearraywithlengthn.Forsimplicity, weassumethatnisapowerof2.Clearly,wehave
T(n).T(n.2)+4:
HenceT(n).O(log2n).O(log2(b;a+1)).Thecorrectnessisjusti.edbythethree-case analysisabove.
1
Problem3:Designanalgorithmfordetectingwhetheranyundirectedgraphisconnected. Provethecorrectnessofyouralgorithmandanalyzeitsrunningtime.Youralgorithmshould bease.cientaspossible.(Thegradingwillbebasedonthee.ciencyandcorrectnessofyour algorithm.) Solution:ForanygivenundirectedgraphG,takeanyvertexsandnameitasthesource vertex.RuntheBFSon(G.s).Thencheckthevaluesd[v]foreachv.Ifd[v].1forsome vertexv,output\disconnected".Otherwiseoutput\connected".
TherunningtimeisthesameastheBFS,i.e.,O(jVj+jEj).Thecorrectnessisjusti.edas follows.Ifthereisapathfromstoeveryothervertex,clearly,thegraphisconnected.Ifthere isnopathfromstosomeothervertex,thenGisdisconnected.HenceGisconnectedifand onlyifthereisapathfromstoeveryothervertex.Thisisequivalenttod[v]61forevery
.vertexv. OtherSolutions:Thesecondsolutionistocheckthecolorofallvertices.Thethirdoneisto countthetotalnumberofverticesvisited.
Problem4:GivenadigraphGwithnverticesandeedges,weruntheDFSonGandobtain aDFSforestFG.Answerthefollowingquestions:
(4.1)ProvethatthenumberofedgesinFGisatmostminfn;1.eg. Solution:LetT1.T2.....TkdenotealltheDFStrees,andletnidenotethenumberof
verticesinTi.Thenthenumberofedgesinthetreeisni;1.Hencethetotalnumberof edgesinFGis
kk
XX
(ni;1).( ni);k.n;k.n;1.
i.1 i.1
becausek.1.Ontheotherhand,thetotalnumberofedgesinFGisatmoste,thetotal numberofedgesinG.HencethenumberofedgesinFGisatmostminfn;1.eg.
(4.2)Isitpossiblethate.n;1andatthesametimeFGhasnoedgeatall.Ifyouranswer isyes,giveanexample.Otherwiseprovethatitisimpossible.
Solution:Ye