=========================preview======================
(COMP171)comp171mds04sol_hung.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 t h e runningtimeoffun(). Obviously,wehave(letn. 2 k),
T(n) .2T(n.2)+O(1)
.4T(n.4)+2O(1)+O(1)
. : : :
.2kT(n.2k) +( 2 k;1+: : : + 2 + 1 ) O(1)
.nT(1)+(2k;1)O(1)
.nO( 1 ) +( n;1)O(1)
.O(n):

2.Thesubsequentarraycontentsare: Initialiation:
0123456 36
28242219149
After1ststep:
0123456 28
22249191436
After2ndstep:
0123456 24
22149192836
After3rdstep:
0123456 22
19149242836
After4thstep:
0123456 19
91422242836
After5thstep:
0123456 14
91922242836
After6thstep:
0123456 9
141922242836
























































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.ndwhereqis.SwapitwiththelastelementofAanduseit
asthepivottopartitionthearrayintotwo.Thisissimilartothequicksort
algorithmasfollows:
A.KeepaleftandrightpointerinA.leftgoesfromlefttoright,until
it.ndsanumberlargerthanorequaltoq.
B.Therightpointeringoesfromrighttoleft,untilit.ndsanumber
smallerthanq(orhitstheleftboundaryofthearray).
C.Swaptheelementspointedbyleftandright.
D.Repeattheprocessuntilleftisontherightofright.
E.Swapqwithleft.
Therankofqistheindexpointedbyleft.
ii. The.rstscantakesO(n)to.ndq.Sincethetotalnumberofstepstakenby
leftandrightisthearraysize,thepartitionstepisO(n).Thereforethe
totalnumberofstepsT1(n).O(n).
Notethatastudentmayalsogothroughthearrayandcountthenumberof
elementslessthanx.ThisalsotakesO(n)time.
(b) i. Firstusepart(a)'salgorithmto.ndtherankofqinT1(n)time.Nowthe
arrayAisdividedintotwopartsA1.A2suchthatA1containsallofthose
elementssmallerthanqanditisonleftofqinarrayAwhereasA2contains
allthoseelementslargerthanqanditisonrightofqinarrayA.Suppose
jA1j.n1andjA2j.n2.Notethatn1+n2.n.AspmustbeinA1,by
usingpart(a)'salgorithm,wecan.ndtherankofpinA1intimeT1(n1).
Similarlywecan.ndtherankofrinA2intimeT1(n2).
ii. FindingtherankofqtakesT1(n).Findindtheranksofp.rtakesT1(n1).T1(n2)
timerespectively.Thus
T3(n).T1(n)+(T1(n1)+T1(n2))
.T1(n)+(O(n1)+O(n2))
.T1(n)+O(n)
.T1(n)+T1(n)
.2T1(n):
(c) i. We.rstsortPinincreasingorder.ThenuseP[k.2]asthepivottopartition
thearrayintotwousingthealgorithmgivenaboveto.ndtherankofP[k.2].