=========================preview======================
(COMP171)cs171mt2003sol.pdf
Back to COMP171 Login to download
======================================================
COMP171
Spring2003
Solutions for the Midterm
1. (a) 1010
(b) 114
(c) Itoutputsthenumb e r ntothebasem.
(d) Let T(n) b e the run-time complexity. Since division and cout takes .(1) time,
weclearlyhave:
T(n) .( O(1)T(n.m) +O(1) ifn.m. otherwise.
Therefore,assumingn.mk
T(n) .T(n.m) +O(1)
.T(n.m2) +O(1)+O(1)
.T(n.mk) + k O (1).
.(k+ 1 ) O(1).
.O(k):
Wehencehave
T(n) .O(logn):
2.Step1.Initializethestack.Readinthein.xexpression. Step2.Getonecharacterfromtheexpression Step3.Ifitisavariable(operand),writeitout.RepeatStep2. Step4.Ifitisa(,pushitintothestack.RepeatStep2. Step5.Ifitisa),popfromthestackallthewayto),writingoutalltheoperators
insequence(donotwriteout(and)).RepeatStep2.
Step6.Ifitisa-or+,keeppoppingthestackifitsoperatoris+,-,^,or*andwrite themoutinsequence.Pushthenewoperatorintothestack.RepeatStep2. Step7.Ifitisa*,keeppoppingthestackifitsoperatoris^or*.Pushthenew*
intothestack.RepeatStep2. Step8.Ifitisa^,pushitintothestack.RepeatStep2. Step9.Ifitisanullcharacter(endofline),popandwriteoutalltheoperatorsin
thestack.
3.(a)Step1.Initializei.1andpi.0.qi.0. Step2.IfA[qi].A[qi+1],wearestartinganincreasingsequenceandsokeep incrementingqiuntilitisnotso(i.e.,whenA[qi].A[qi+1])orqiequalto n;1. Step3.Otherwise,wehaveA[qi].A[qi+1]andhencewestartadecreasing sequence.Thenkeepincrementingqiuntilitisnotso(i.e.,whenA[qi]. A[qi+1])orendofarray. Step4.Incrementi.Setpi.qi.qi;1+1.Ifpi.nexit.otherwise,repeat Step2.
(b)WecallanelementA[i]ofAalocalmaximum(resp.,localminimum)ifandonly ifA[i].A[i;1]andA[i].A[i+1](resp.,A[i].A[i;1]andA[i].A[i+1]). Thealgorithmhasthefollowingsteps.
Step1.ScanthearrayAto.ndoutalllocalmaximaandlocalminima.This takesO(n)time.NotethatsinceAisaconcatenationofksortedsubarrays, thereareonlyO(k)suchlocalmaxima/minima.
Step2.DividearrayAintosubarraysbycuttingAateachsuchlocalmaximum andlocalminimum.ThistakesO(n)time.Notethattheresultofthis divisionofAisO(k)subarraysA1.A.:::.AK,suchthateachsuchsubarray
2
Aiisinasorted(increasingordecreasing)order,andK.O(k). Step3.ForeachsubarrayAi,ifAiisindecreasingorder,thenreverseAiinto INCREASINGorder.ThistakesO(n)timeforallsubarrays. Step4.GrouptheKsubarraysintoK0.dK.2epairs(thelast"pair"mayhas onlyonesubarray),andmergethetwosubarraysineachpair. Step5.LetK.K0andrepeatSteps4and5,untilK0.1.Notethatwhen K0.1,thereisonlyonesortedsubarray,whichisA.
(c)NotethatSteps4and5willberepeatedO(logk)times,andperformingSteps4 and5eachtimetakesO(n)time. Summingoverallthestepsabove,thetotaltimeofthealgorithmisO(nlogk).
(d)TherearemanyvaluesofksuchthatkisnotaconstantandO(nlogk).6
p
.(nlogn).Forexample,whenk.logn,k.(logn)logn ,k.loglogn,etc.In general,onecanchooseanarbitraryvaluek.o(nc)foranyconstantc.0(and c.1).thatis,kis\small-oh"ofncforanyc.0.
4.(a)Thearray29,12,17,10,11,16,16,9,7,10,11 (b)Thearray11,11,12,11,19,37,13,15,1411,11,12,14,11,37,13,15,19
or
5.We.rstsortthearraysAandBindependentlyusingQuicksort.ThistakesO(nlogn) timeintheworstcase(usingm