=========================preview======================
(COMP171)comp171_96s_final.pdf
Back to COMP171 Login to download
======================================================

2.(10marks)
3.(10marks)
Indoublehashingeachkeyhastwoassociatedvalues:itshashaddressanditsincrement.

Wede.nedtwoperformancemeasuresIPLandEPLforbinarysearchtreesthatgivethetotal Youaregiventhefollowingkeys
numberofnodevisitsforallkeysinatreeandforallgapsinatree,respectively.Inasimilar manner,wede.neInternalComparisonCount(ICC)andExternalComparisonCount(ECC) 24.16.38.76.15.43.30.79.63.49
asfollows:
X
ICC(T). compno(u)
andthefollowingtwohashfunctionsthatgivethehashaddressandtheincrement:

internalnodesu
and
X
h(X).2Xmod11
ECC(T). compno(u)
externalnodesu
and
thatdependonthenumberofkeycomparisonsthatleadustoeachnode.

g(X).(Xmod10)+1: Assumethatthesearchalgorithmalways.rsttestswhetherasearchkeyislessthananode's
Insertthekeysoneatatimeintothehashtableandshowthesnapshotsaftereachinsertion. keyand,ifitisnot,testsforequality:the(...)scheme.Then,branchingleftfromanode
wehavegivenyouasequenceofhashtablessothatyoucanshowthesnapshotseasily.Give takesonekeycomparison,whereasbranchingrightandterminatingatanodetakestwokey
thetotalnumberofprobestakenbythesequence.
comparisons.Detectingthatanodeisexternaltakeszerokeycomparisons.

T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
0
1
2
3
4
5
6
7
8
9
10
Probes

(a)GivetheIPL,theEPL,theICC,andtheECCofthefollowingtwotrees:
.... ....
.J .J
..
JJ
JJ.. ..

..J....J..
.J .J

........
.
B.
B .
B.
B .B.B .B.B .B.B .B.B

... ... ..
B
.B
.B B

......
.
B .
B.
B .B .B.B .B .B.B
..B B
.B
.. ..
.
B
.B .B .B

Totalprobes.
3 4






10.(10marks)YouarethechiefsoftwareengineerinUSTConsulting,alocalcompany.Lastweek youtalkedwiththesoftwarecompanyBEFORE.BEFOREarehavinge.ciencyproblemswith FMS,a.lemanagementsystem,thattheyhaddesigned,implementedandinstalled.Itis designedtohandlelarge.lesof100,000ormorerecords.Ithasawellwell-designeduser interfaceanditisstable,fewerrorshavebeenreported.Theproblemisthatalthoughmost ofBEFORE'scustomershavenocomplaintswiththesystem,twoofthem,AandB,havea seriouscomplaint.
FMSallowsuserstoinitializea.lesystemwithanynumberofrecordsanddoitfast.It providesretrievalonakeyandallrecordshaveuniquekeys.Itallowsinsertionsofnew recordsanddeletionofrecordsthatarenolongerneeded.Inaddition,ithasmanyother options.
AandBrepresenttwoextremecases.CompanyAalwayshaslessthan10,000recordsand theirrecordsaresmall,lessthan100bytesinsize.Thesearchandupdatetimearetooslow forthemcomparedtotheirpreviousMacrohardsystem.CompanyBistheoppositeextreme, theyareoneofahandfulofBEFOREcustomerswhoarehandlingmorethan100,000records. Theyarealsocomplainingaboutspeed.
AftersomediscussionwithBEFOREaboutFMS,youdiscoveredthatitisadisk-basedsystem thatusesbalancedbinarysearchtreestorepresentthe.les.
WhatwouldyousuggestthatBEFOREshoulddotoalleviateorsolvebothAandB'sprob-lems.StateseparatelyforAandByoursuggestedstrategiesandjustifythem.Addressthe issueofwhetheryoucanhelpbothAandB.
17