=========================preview======================
(COMP171)comp171mds04sol_cloud.pdf
Back to COMP171 Login to download
======================================================
COMP171
Spring2004

Solutions for the Midterm
1. (a) 7
(b) 0
(c) Itreturnsthearrayindexofthemaximumelement.
(d) LetT(n)b e th e runningtimeoffun(). Obviously,wehave(letn. 2 k),
T(n) .2T(n.2)+O(1)
.4T(n.4)+2O(1)+O(1)
. :::
.nT(1)+(n;1)O(1)
.nO(1)+(n;1)O(1)
.O(n):

2.Thesubsequentarraycontentsare: Initialiation:
0123456 9
191422282436
After1ststep:
0123456 14
1924222836
After2ndstep:
0123456
1922243628
After3rdstep:
0123456
22282436
After4thstep:
0123456
242836
After5thstep:
0123456 28
36
After6thstep:
0123456 36
























































3. (a) To implement the Stack ADT using two queues, Q1 and Q2,we can simply
enqueueelementsintoQ1wheneverapushcallismade.
Forpopcalls,wecandequeueallelementsofQ1andenqueuethemintoQ2except
forthelastelementwhichwesetasideinatempvariable. Wethenreturnthe
elements to Q1 by dequeing from Q2 and enqueing into Q1.The last element
thatwesetasideearlieristhenreturnedastheresultofthepop.
Note: Thestudentsmaysimplyreturnthelastelement in Q1andinnextopera-
tion,therolesofQ1andQ2 w ouldb e sw apped.
(b) ThepushtakesO(1)timetocomplete. PerformingapoptakesO(n)time.
Thereforefornp op s andpushes,ittakesO(n2)steps.

4. (a) i. Scanaonceto.ndwherexis.Swapitwiththelastelementofaanduseit
asthepivottopartitionthearrayintotwo.Thisissimilartothequicksort
algorithmasfollows:
A.Keepaleftandrightpointerina.leftgoesfromlefttoright,until
it.ndsanumberlargerthanorequaltox.
B.Therightpointeringoesfromrighttoleft,untilit.ndsanumber
smallerthanx(orhitstheleftboundaryofthearray).
C.Swaptheelementspointedbyleftandright.
D.Repeattheprocessuntilleftisontherightofright.
E.Swapxwithleft.
Therankofxistheindexpointedbyleft.
ii. The.rstscantakesO(n)to.ndx.Sincethetotalnumberofstepstakenby
leftandrightisthearraysize,thepartitionstepisO(n).Thereforethe
totalnumberofstepsisO(n).
Notethatastudentmayalsogothroughthearrayandcountthenumberof
elementslessthanx.ThisalsotakesO(n)time.
(b) i. We.rstsortbinincreasingorder.Thenuseb[k/2]asthepivottopar-
titionthearrayintotwousingthealgorithmgivenaboveto.ndtherank
ofb[k/2].Nowfortheleftsub-arrayofa,weneedto.ndtheranksof
b[0...k/2-1],whereasfortherightsub-arrayofa,weneedto.ndsthe
ranksofb[k/2+1...k-1].
Foreachofthesesub-arrays,werecursivelypartitionituntilalltheranksof
barefound.
ii. ThesortingpartonbisO(klogk).Dividingthearrayofsizenintotwo
partstakesO(m)runningtime,wheremistheoriginalsizeofthearraytobe
divided.WeshowinFigure1thedivide-and-conquerstepsofthealgorithm,
whereeachstepdividesthearrayintotwousingtheentriesinb:


Figure1:Divide-and-conquerstepsfortherankproblem.
Clearly,therearelogklevels,andeachleveltakesatotalofO(n)stepsin theworstcase.Thereforethetotalworst-caserunningtimeofthealgorithm isO(klogk)+O(nlogk).O(nlogk).Notethattheresultis