=========================preview======================
(COMP271)1997Spring_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
TheHongKongUniversityofScience&Technology
DepartmentofComputerScience
COMP271,Section1:DesignandAnalysisofAlgorithms
mid-termexamination
Date:4:30-6:30p.m.,3April,1997.
Venue:LTB

Studentname: StudentID: e
mail:
Question
1
2
3
4
Total
Grade
/12pts
/12pts
/12pts
/12pts
/48Pts
Problem1
Answerthefollowingshortquestions.
(a)Foreachpartofexpressions(A.B)below,indicatewhetherAisO,.,or.ofB.Note

thatzero,oneormoreoftheserelationsmayholdforagivenpair.listallcorrectones.No
explanationisneeded.
(i)A.(n+a)b ,B.nb.aandbarerealconstants.0.
A.O(B).A..(B).A..(B):

n+c.
(ii)A.3n ,B.3cisarealconstant.0. A.O(B).A..(B).A..(B):
(iii)A.O(f(n)),B.O(f(n)).forsomefunctionf(n). norelation (iv)A..(f(n)),B..(f(n)).forsomefunctionf(n). norelation (b)Showhowtosortnintegersintherange1ton2inO(n)time.Yourneednottoargue
thecorrectnessandrunningtimeofyouralgorithm. Observethefactthatanintegerintherange[0:::n2;1]canbewrittenasa2-tupleof base-ndigits,eachintherange[0:::n;1].Moreformally,anyintegervin0ton2;1, canbewrittenas.c.c.suchthat
10
v.c1n+c0:

whereeachc1andc0isintherange[0:::n;1].Thec1andc0canbefoundbythefollowing standardbase-reductionprocedure,whichconvertsanumberv2[0:::n2;1]into2digits basen:
Digits(v,n,2)f
j.0.
forj.0to1dof
c[j++].v%n.
v.v/n.
g
returnc[0.1].
g
Wecanapplytheradixsort,stablysortingeachofthe2base-ndigitsinleasttomost signi.cantorder.EachsortingiterationtakesO(n)timeandthenumberofdigitsisk. ThereforeO(2n)timeistakenaltogether.i.e.,O(n)runningtime.
(c)Considerthefollowingrecurrencerelation,
(
1ifn.1.
T(n).2T(bnc)+nifn.1.
2
(i)Mr.CarelessusethesubstitutionmethodtoarguetheT(n).O(n).Heguesses T(n).cnforsomeconstantc.Clearly,T(1).1.c.1forsomeconstantc.1.Hereis hisinductivestep,
T(n).2T(bnc)+n
2
.2(cbnc)+n(usetheinductivehypothesis)
2
.cn+n
.O(n).

Discussbrie.ywhyhisproofisnotcorrect.
Hehasnotprovedtheexactformoftheinductivehypothesis,thatisT(n).cnforsome constantc.
(ii)Usingthesubstitutionmethodorothermethodstosolvetherecurrencerelation.



Problem2
Givenasequenceofnumbersa1.a2.:::.an,andanintegeri,1.i.n,computethei-th smallestelement.Thisiscalledtheselectionproblem.
(a)GiveaO(nlogn)algorithmforthisproblem.Youneednottoprovethecorrectnessand runningtimeofyouralgorithm.
Wecansortthennumbersusingmergesort(oranyotherO(nlogn)sortingalgorithm)in ascendingorder.Wethencanreportthei-thsmallestnumberinO(1)time.Therefore,the totalrunningtimeisO(nlogn).
(b)Mr.Carelessproposesthefollowingrandomziedalgorithmtotheproblem.
procedureSelect(A[p:::r].i)
f
if(p..r)return(A[p]).
q.RandomizedPartition(A[p:::r]).
k.q-p+1.
if(i..k)return(A[q]).
if(i.k)returnSelect(A[p:::q].i)).
elsereturnSelect(A[q+1:::r].i). g
TheprocedureRandomizedPartition(A[p:::r])willrandomlyselectanelementxfrom thelistA[p:::r],calledthepivot.Itthenpartitionstheelementsintotwosubarrays, A[p:::q;1]containstheelementlessthanorequaltox,A[q].xandA[q+1:::r] containstheelementgreaterthanorequaltox.