=========================preview======================
(COMP171)2002_spring_midterm_exam_solution.pdf
Back to COMP171 Login to download
======================================================
p
1.Oneanswerisf(n).nloge n.Therearefourjusti.cationsneeded.(i)Sinceg(n).f(n)forn.3,
p
g.O(f).(ii)ontheotherhandf(n).g(n).loge nwhichdivergesto1.Thereforeforevery K.0thereisanNsothatf(n).g(n).K,alln.N.Thismeansthattherecannotbeany.nite constantc.0forwhichf(n).cg(n)forsu.cientlylargen,sof6g..(f).(iii)
.O(g),implying6p
sincef(n).h(n)forn.3,f.O(h).(iv)f6..(h)becauseh(n).f(n).lognwhich,asin (ii)showsthenumeratorfunctiontogrowstrictlyfaster.
Thereareseveralgeneralwaystocreatefunctionswhosegrowthrateisstrictlybetweentheratesof functionsg(n)andh(n),assumingbothg.h!1asn!1andthatg.O(h)butg.6.(h).One istode.nef(n).(g(n))t(h(n))1;t ,t2(0.1).Theaboveanswerusest.1.2.
Anotherwayistotaker(n).h(n).g(n),.ndafunctionc(n)thatdivergesto1atastrictlyslower ratethanr(n),andthenusef(n).c(n).g(n).Inourexampler(n).lognandwecoulduse
p
c1(n).lognorc2(n).loglogn.
2.AsimpleapproachistocompareeverysubstringL[i]inLwithstringS.LetlbethelengthofL[i]. WematchL[i]withS[1::landifwefail,thenwematchL[i]withS[2::l],etc.(Forthispurpose,we needtocomputethelengthlofL[i].)IfL[i]appearsinS,thenwecomparelwiththebestanswerso farandupdatethebestansweraccordingly.ThetimecomplexityofthisapproachisO(mn`).The detailsaregiveninthefollowingalgorithm.
AlgorithmMatch(S.L)
Input:S[1::n]containsthestringandL[1::`.1::m]containsthelibraryofsubstrings.
Output:Thelengthandthepositionofthelongestmatch.
1.position:.0.length:.0.
2.for1.i.`
3.domatch:.false.
4.pos:.0.
5.len:.0.
6.for1.j.mandL[i.j]6.$

7. dolen:.len+1.
8.for1.k.(n;len+1)andmatch.false

9.
domatch:.true.

10.
pos:.k.

11.
for1.j.len

12.
doifL[i.j].6S[k+j]


13. thenmatch:.false.
14.ifmatch.trueandlen.length
15.thenposition:.pos.

16. length:.len.
17.ifposition6.0
18.thenoutput(position,length).
19.elseoutput\nomatch".

Onecanimprovetheaboveapproachby.rstsortingthesubstringsinLinincreasingorderoflength beforeexecutingtheabovealgorithm.OnceL[i]isfoundtoappearwithinSforsomei,wedonot needtoexaminetheremainingsubstringsinL.ThesortingpreprocessingwilltakeO(m`+`log`) time.TheO(m`)termcomesfromcountingthelengthofeachsubstringinLandtheO(`log`)term comesfromsorting.
3.
(a)6,3,1,5,4,12,10,7,9,8,14,13
(b)1,4,5,3,8,9,7,10,13,14,12,6

4.
(a)
i.


ii.

(b)Givenamax-heap,thelargestvalueisstoredattheroot,i.e.,A[0].SowereportA[0]asthe largestvalue.Bythemax-heapproperty,thesecondlargestvalueisstoredatachildofthe root,i.e.,A[1]orA[2].SowecompareA[1]withA[2]andreportthelargeroneasthesecond largestvalue.Ittakesonecomparison.
(c)WereplacethecontentofA[i]byx.Thenwerepeatthefollowinguntilwearedone:
i.IfA[i]issmallerthanitsparent,weswapitwithitsparenandseti.bi.2c.Ifibecomes zero,thenwearedone. ii.IfA[i]islargerthansomechild,weswapitwiththechildwiththesmallervalueandseti tobetheindexofthatchild.IfthenewA[i]doesnothaveanychild,thenwearedone. iii.Otherwise,A[i]isinthecorrectpositionandwearedone.
TherunningtimeisO(logn).
5.
(a)



(b)Sincetheroothastwochildren,todeleteit,wereplace