Study Guides (380,000)
CA (150,000)
Carleton (5,000)
COMP (50)
Final

Theorem Study Notes


Department
Computer Science
Course Code
COMP 2402
Professor
Pat Morin
Study Guide
Final

This preview shows pages 1-3. to view the full 9 pages of the document.
DataStructureTheorems
ArrayStack:
AnArrayStackimplementstheListinterface.Ignoringthecostsofresize(),
get(i)andset(i,x)executeinO(1)timeperoperationandadd(i,x)andremove(i)
executeinO(1+ni)timeperoperation.Furthermore,startingwithanempty
ArrayStack,anysequenceofmadd(i,x)andremove(i)resultsinatotalofO(m)
timeduringallcallstoresize().
● ArrayDeque:Allowsustoefficientlyaddtooneendofthesequenceandremovefrom
theotherend.Usescirculararraytechnique.
AnArrayDequeimplementstheListinterface.Ignoringcostsofcallstoresize(),
get(i)andset(i,x)runinO(1)timeperoperation,andadd(i,x)andremove(i)
executeinO(1+min{i,ni})timeperoperation.Furthermore,beginningwith
anemptyarray,performinganysequenceofmadd(i,x)andremove(i)
operationsresultsinatotalofO(m)timespentduringcallstoresize().
DualArrayDeque:AchievesameperformanceboundasanArrayDequeusing2
ArrayStacks.SinceanArrayStackisfastatmodifyingelementsattheend,a
DualArrayDequeplaces2ArrayStacks,calledfrontandback,backtobacksothat
operationsarefastateitherend.Thefrontstorestheelementswhoseindicesare
0,...,front.size()1,butstorestheminreverseorder.Thebackstoreselementswith
indicesfront.size(),...,size()1inthenormalorder.Thefrontandbackcontainatleast
n/4elements.Rebalancingmakesthefrontandbackcontainexactlyn/2elements
each.
ADualArrayDequeimplementstheListinterface.Ignoringthecostofcallsto
resize()andbalance(),aDualArrayDequesupportstheoperationsget(i)and
set(i,x)inO(1)timeperoperation;andadd(i,x)andremove(i)inO(1+min{i,
ni})timeperoperation.Furthermore,beginningwithanempty
DualArrayDeque,anysequenceofmadd(i,x)andremove(i)operationsresults
inatotalofO(m)timespentduringallcallstoresize()andbalance()
*Seemsingeneralthatgrowing,shrinking,orrebalancingArrayBasedlistsmovesn
elementsinO(n)time.O(m)timeisspentintotaltoallthecallstothesemethodsformadd()
andremove()operations
● RootishArrayStack:Aspaceefficientarraystack.StoresnelementsusingO( )
n
arrays.TheywasteatmostO( )space.Storeselementsinlistofarrayscalled
n
blocks,eachcontainingb+1elements.Isfullifr(r+1)/2=n.Afteracalltogrow()or
shrink(),thefinalarrayisempty.Anothercalltogrow()orshrink()won’toccuruntilr1
elementsareaddedorremoved.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

ARootishArrayStackimplementstheListinterface.Ignoringthecostofcallsto
grow()andshrink():
■ get(i)andset(i,x)runinO(1)timeperoperation
■ add(i,x)andremove(i)runinO(1+ni)timeperoperation
Furthermore,beginningwithanemptyRootishArrayStack,anysequenceofmadd(i,x)
andremove(i)operationsresultsinatotaltimeO(m)spentincallstogrow()and
shrink().ThespacedusedbyaRootishArrayStackstoringnelementsisn+O( )
n
SLList:push()andpop()addandremoveelementsattheheadofthesequence.
add()putsnewelementatthetailandremove()removesthehead.Eachnodeuhas
referencetothenode,u.next,thatfollowsit
○ ASLListimplementstheStackandFIFOQueueinterfaces.Thepush(x),pop(),
add(x)andremove()operationsruninO(1)timeperoperation
DLList:Eachnodeuhasreferencestothenodeu.nextthatfollowsitandu.prevthat
precedesit.Thedummynodeprecedesthefirstelementandfollowslastelement.
ADLListimplementstheListinterface.Inthisimplementation,get(i),set(i,x),
add(i,x)andremove(i)operationsruninO(1+min{i,ni})timeperoperation.If
thecostofgetNode(i)isignored,thenalloperationsruninconstanttime.Thus,
onlyexpensivepartofDLListoperationsisfindingtherightnode.
*Adrawbackoflinkedlistsistherespaceusage.EachnodeinaDLListrequiresanadditional
2referencestothenextandpreviousnodesinthelist
SEList(Spaceefficientlinkedlist):EachindividualnodeinaSEListstoresa
BDeque(boundeddeque,adds/removesfromfront/backinconstanttime)blockwhich
canholduptob+1elements.Unlessablockisthelastblock,thenitcontainsatleast
b1andatmostb+1elements.
AnSEListimplementstheListinterface.Ignoringthecostofcallstospread(u)
andgather(u),anSEListwithblocksizebsupportstheoperations
■ get(i)andset(i,x)inO(1+min{i,ni}/b)timeperoperation
■ add(i,x)andremove(i)inO(b+min{i,ni}/b)timeperoperation
Furthermore,beginningwithanemptySEList,anysequenceofmadd(i,x)and
remove(i)operationsresultsinatotalofO(bm)timespentduringallcallstospread(u)
andgather(u)
ThespaceusedbyanSEListthatstoresnelementsisn+O(b+n/b)
SkipList:AskiplistisasequenceofsinglylinkedlistsL0,...,Lh.EachlistLrcontainsa
subsetoftheitemsinLr1.StartwiththeinputlistL0,containingnitems.Foran
elementx,theheightofxisthelargestvalueofrsuchthatxisinLri.e.Elementswith
aheightof0,onlyappearinL0.Theheightofaskiplististheheightofitstallestnode.
Attheheadofeachlistisaspecialnodecalledthesentinelthatactsasadummy

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

nodeforthelist.Askiplisthasashortpathcalledthesearchpathfromthesentinelin
LhtoeverynodeinL0.
Lemma:Theexpectedlengthofthesearchpathforanynode,u,inL0isat
most2logn+O(1)=O(logn)
● SkipistSSet:
SkiplistSSetimplementstheSSetinterface.ASkiplistSSetsupportsthe
operationsadd(x),remove(x),andfind(x)inO(logn)expectedtimeper
operation
● SkiplistList:
○ ASkiplistListimplementstheListinterfaceandsupportstheoperationsget(i),
set(i,x),add(i,x),andremove(i)inO(logn)expectedtimeperoperation.
● AnalysisofSkiplist:
Lemma:LetTbethenumberoftimesafaircoinistosseduptoandincluding
thefirsttimethecoincoincomesupheads.ThenE[T]=2
Lemma:TheexpectednumberofnodesinaSkiplistcontainingnelements,not
includinginstancesofthesentinel,is2n
Lemma:theexpectedheightofaSkiplistcontainingnelementsisatmostlogn
+2
Lemma:Theexpectednumberofnodesinaskiplistcontainingnelements,
includingalloccurrencesofthesentinelis2n+O(logn)
Theorem:AskiplistcontainingnelementshasexpectedsizeO(n)andthe
expectedlengthofthesearchpathforanyparticularelementisatmost2logn+
O(1)
ChainedHashTable:useshashingwithchainingtostoredataasanarray,t,oflists.
Sotheaverage#ofelementsstoredinoneoftheselistsis ./t.length 1n≤  
○ AChainedHashTableimplementstheUSetinterface.Ignoringthecostofcalls
togrow(),aChainedHashTablesupportstheoperationsadd(x),remove(x),and
find(x)inO(1)expectedtimeperoperation.Furthermore,beginningwithan
emptyChainedHashTable,anysequenceofmadd(x)andremove(x)
operationsresultsinatotalofO(m)timespentduringallcallstogrow()
MultiplicativeHashingEfficientmethodofgeneratinghashvaluesbasedon
modulararithmeticandintegerdivision
■ hash(x)=((z*x)mod2w)div2wd
Lemma:Letxandybeany2valuesin{0,..,2w1}withxy.Then
Probability{hash(x)=hash(y)}2/2d
Lemma:Foranydatavaluex,theexpectedlengthoflistt[hash(x)]isat
mostnx+2,wherenxisthethenumberofoccurrencesofxinthehash
table
■ Code:
You're Reading a Preview

Unlock to view full version