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(),
executeinO(1+ni)timeperoperation.Furthermore,startingwithanempty
timeduringallcallstoresize().
theotherend.Usescirculararraytechnique.
AnArrayDequeimplementstheListinterface.Ignoringcostsofcallstoresize(),
executeinO(1+min{i,ni})timeperoperation.Furthermore,beginningwith
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
ni})timeperoperation.Furthermore,beginningwithanempty
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
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

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
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
referencetothenode,u.next,thatfollowsit
○ ASLListimplementstheStackandFIFOQueueinterfaces.Thepush(x),pop(),
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),
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.
2referencestothenextandpreviousnodesinthelist
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.
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
andgather(u)
ThespaceusedbyanSEListthatstoresnelementsisn+O(b+n/b)
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.

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
operation
● SkiplistList:
○ ASkiplistListimplementstheListinterfaceandsupportstheoperationsget(i),
● AnalysisofSkiplist:
Lemma:LetTbethenumberoftimesafaircoinistosseduptoandincluding
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
find(x)inO(1)expectedtimeperoperation.Furthermore,beginningwithan
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:

Unlock to view full version