Introduction to Algorithms
Introduction to Algorithms COT 5407
Popular in Course
Popular in Engineering and Tech
Dr. Tyrell McKenzie
verified elite notetaker
This 16 page Class Notes was uploaded by Angelina Ankunding on Monday October 12, 2015. The Class Notes belongs to COT 5407 at Florida International University taught by Tao Li in Fall. Since its upload, it has received 24 views. For similar materials see /class/221842/cot-5407-florida-international-university in Engineering and Tech at Florida International University.
Reviews for Introduction to Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
Chapter 17 Amortized Analysis Today we study amortized analysis C L S 2 What is that master Efficiency averaged over time That is right boy C L S 2 We assume that a sequence of operations is executed on a data structure and calculate C L S the cost per operation U averaged over the sequence Does it mean that some operations are cheap and some are expensive depending on the situation That s right C L S f Our first example is Multip0p a new operation on a stack With this you are able to pop any number of elements from C L S a stack 2 However it is implemented by repeated execution of Pop What are the other 3 permissible operations Creation of an empty stack Push Pop and Empty which C L S tests the emptiness U Ostensibly Multipop is quite expensive because elimination of k objects requires 0k steps However for us to be able to h w eliminate k objects Push has to be executed at least is times prior to that Which means a bad thing does not happen so very often Our next example is a kbit binary counter Suppose we will increment n C L S times a kbit counter that is U initially set to O a The number of bit operations required is high if there is a quotiii 0 long run of 1 s at the lower g bits of the counter but that does not happen very often That is right C L S f Amortized Analysis Suppose that n operations chosen from Pop Push and Multipop are executed on an initially empty stack The total cost for Multipop is the linear function of the total number of Push which is at most n So the amortized cost of Multip0p is 01 Suppose that a kbit counter initially set to O is incremented n times The total number of bit flips on the counter is 9 n 00 nj 1 i0 22 i0 22 So the amortized cost is 01 This calculation method is called aggregate method The potential method Policy For each 239 1 g 239 g n let Ci be the actual cost of the ith operation and Di be the data structure when the ith operation has been done Pick a potential function CD that assigns a value to the data structure and define the amortized cost 6i as Ci clgtDi clgtDi1 Let Tn 231 Q be the total amortized cost Then TC 2 Ci Di CDCDi i1 i Ci Dn clgtDo i1 We ll pick CD so that o for all 239 clgtDi 2 clgtDO and o 2amp1 6i is easy to compute Then Tnn gives an upperbound for the amortized cost So we will evaluate 6i instead of Ci A Stack Define Di to be the stack size Then DO O and so for all 2392 1 Di 2 cN130 The amortized cost Q is 1 1 2 for Push and O for both Pop and Multipop B Counter Define Di to be the number of bits 1 in the counter after the ith incrementation Then cigtDO O and for all 239 2392 0 ltDD2 2 0 Define ti to be the number of bits that are reset at the ith operation Then for all 239 2 O Di1 S ti 1 Then Ci 2 ti 1 and Q gti11 ti2 So the amortized cost is 01 10 Dynamic Tables A dynamic table is a table of variable size where an expansion or a contraction is caused when the load factor has become larger or smaller than a fixed threshold Let the expansion threshold be 1 and the expansion rate be 2 Le the table size is doubled when an item is to be inserted when the table is full Let the contraction threshold be and the contraction rate be ie the table size is halved when an item is to be eliminated when the table is exactly one fourth full 11 Implementation of Expansion amp Contraction When these operations take place we create a new table and move all the elements from the old one to the new one Suppose that there are n calls of insertion and deletion are made what is the average cost of each operation 12 If the size is kept the same the cost is 01 If the size is doubled from M to 2M the actual cost is M 1 The time that it takes for the next table size change to occur is at least M steps for doubling and at least M2 steps for halving So the actual cost can be spread over the next M2 quotnormalquot steps This gives an amortized cost of 01 If the size is halved from M to M2 the actual cost is M4 The time that it takes for the next table size change to occur is at least steps for doubling and at least steps for halving So the actual cost can be spread over the next M8 steps to yield an amortized cost of 01 13 Amortized Cost Analysis Using the Potential Method For each 239 1 g 239 g n define c to be the number of insertions and deletions that are executed at the ith operation and define 27mm size if 052 2 df cm 7mm if 05239 lt Here size is the table size mum is the number of elements in the table and oz is the ratio after the ith operation Note that a at time 0 the table is empty so CDO O o for all 239 CD 2 O and thus Cbn 2 CDC and o clgtn 3 2n n n so the contribution of the potential function to the amortized cost is at most 1 l4 The Amortized Cost Q for Insertion Here m numi1 and s sizezgl a 05241 1 Here m 3 Ci Di Di1 5239 m4 20n1y 2m 3H3 b om lt 1 Caquot Di Di1 1 20n1 3 Zn 3H3 c ozi2 Herem1 Caquot 2 Di1 1 20n1 3 2 n dozilt 02 Di Di1 1 32 m 1 32 mH 0 So the amortized cost of insertion is 01 15 The Amortized Cost Q for Deletion a 04239 2 3 Caquot Di CDil 5239 12m 1 s2m sH 1 CZ CD2 cDil 1 3 m 1 2m 3H 2 C 4lt042 1S 02 Di Dz1 1 32 m 1 32 mH 2 d IN Z m and azlt 62 pi Dz1 So the amortized cost of deletion is 01 16
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'