Question? Leave a message!




Data structures

Data structures
DATA STRUCTURES I, II, III, AND IV I. Amortized Analysis II. Binary and Binomial Heaps III. Fibonacci Heaps IV. Union–Find Lecture slides by Kevin Wayne
 http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on 1/24/17 11:31 AMData structures Static problems. Given an input, produce an output. Ex. Sorting, FFT, edit distance, shortest paths, MST, maxflow, ... 
 Dynamic problems. Given a sequence of operations (given one at a time), produce a sequence of outputs. Ex. Stack, queue, priority queue, symbol table, unionfind, …. 
 Algorithm. Stepbystep procedure to solve a problem. Data structure. Way to store and organize data. Ex. Array, linked list, binary heap, binary search tree, hash table, … 7 1 2 3 4 5 6 7 8 33 22 55 23 16 63 86 9 33 10 44 86 33 99 1 4 1 3 ● ● ● ● 46 83 90 93 47 60 2Appetizer Goal. Design a data structure to support all operations in O(1) time. INIT(n): create and return an initialized array (all zero) of length n. th READ(A, i): return i element of array. th WRITE(A, i, value): set i element of array to value. 
 true in C or C++, but not Java Assumptions. Can MALLOC an uninitialized array of length n in O(1) time. th Given an array, can read or write i element in O(1) time.
 Remark. An array does INIT in O(n) time and READ and WRITE in O(1) time. 3Appetizer Data structure. Three arrays A1.. n, B1.. n, and C1.. n, and an integer k. Ai stores the current value for READ (if initialized). k = number of initialized entries. th Cj = index of j initialized entry for j = 1, …, k. If Cj = i, then Bi = j for j = 1, …, k. 
 Theorem. Ai is initialized iff both 1 ≤ Bi ≤ k and CBi = i. Pf. Ahead. 1 2 3 4 5 6 7 8 A 22 55 99 33 B 3 4 1 2 4 6 2 3 C k = 4 A4=99, A6=33, A2=22, and A3=55 initialized in that order 4Appetizer INIT (A, n) READ (A, i) WRITE (A, i, value) k ← 0. IF (INITIALIZED (Ai)) IF (INITIALIZED (Ai)) A ← MALLOC(n). RETURN Ai. Ai ← value. B ← MALLOC(n). ELSE ELSE RETURN 0. C ← MALLOC(n). k ← k + 1. Ai ← value. Bi ← k. Ck ← i. INITIALIZED (A, i) IF (1 ≤ Bi ≤ k) and (CBi = i) RETURN true. ELSE RETURN false. 5Appetizer Theorem. Ai is initialized iff both 1 ≤ Bi ≤ k and CBi = i. Pf. ⇒ th Suppose Ai is the j entry to be initialized. Then Cj = i and Bi = j. Thus, CBi = i. 1 2 3 4 5 6 7 8 A 22 55 99 33 B 3 4 1 2 4 6 2 3 C k = 4 A4=99, A6=33, A2=22, and A3=55 initialized in that order 6Appetizer Theorem. Ai is initialized iff both 1 ≤ Bi ≤ k and CBi = i. Pf. ⇐ Suppose Ai is uninitialized. If Bi 1 or Bi k, then Ai clearly uninitialized. If 1 ≤ Bi ≤ k by coincidence, then we still can't have CBi = i
 because none of the entries C1.. k can equal i. ▪ 1 2 3 4 5 6 7 8 A 22 55 99 33 B 3 4 1 2 4 6 2 3 C k = 4 A4=99, A6=33, A2=22, and A3=55 initialized in that order 7AMORTIZED ANALYSIS binary counter ‣ multipop stack ‣ dynamic table ‣ Lecture slides by Kevin Wayne
 http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on 1/24/17 11:31 AMAmortized analysis Worstcase analysis. Determine worstcase running time of a data structure operation as function of the input size. can be too pessimistic if the only way to 
 encounter an expensive operation is if there were lots of previous cheap operations 
 
 
 Amortized analysis. Determine worstcase running time of a sequence of data structure operations as a function of the input size. 
 Ex. Starting from an empty stack implemented with a dynamic table, any sequence of n push and pop operations takes O(n) time in the worst case. 9Amortized analysis: applications Splay trees. Dynamic table. Fibonacci heaps. Garbage collection. Movetofront list updating. Pushrelabel algorithm for max flow. Path compression for disjointset union. Structural modifications to redblack trees. Security, databases, distributed computing, ... SIAM J. ALG. DISC. METH. 1985 Society for Industrial and Applied Mathematics Vol. No. April 1985 016 6, 2, AMORTIZED COMPUTATIONAL COMPLEXITY ROBERT ENDRE TARJANt Abstract. A in the powerfultechnique complexity analysisofdatastructures is amortization,oraveraging over time. Amortized running time is a realistic but robust measure for which we can obtain complexity and lower bounds on a of the of surprisingly tight upper variety algorithms. By following principle designing whose amortized is we algorithms complexity low, obtain "selfadjusting" data structures that are simple, flexible and efficient. This paper surveys recent work by several researchers on amortized complexity. ASM(MOS) subject classifications. 68C25, 68E05 10 1. Introduction. Webster’s defines "amortize" as "to aside at 34 put money intervals, as in a sinking fund, for gradual payment of (a debt, etc.)."We shall adapt this term to computational it "to over time" or, more complexity, meaning by average precisely, "to average the times of operations in a over thesequence." running sequence The following observation motivates our of amortization: In many uses of data study structures, a sequence of rather than just a single operation, is performed, operations, and we are interested in the total time of the sequence, rather than in the times of the individual operations.A worstcase in which we sum the worstcase times analysis, of the individual operations, may be unduly because it ignores correlated pessimistic, effects of the operations on the data structure. On the other hand, an averagecase analysis may be inaccurate, since the probabilistic assumptions needed to out carry the analysis may be false. In such a situation, an amortized in which we analysis, average the running time per operation over a (worstcase) sequence of operations, can yield an answer that is both realistic and robust. To make the idea of amortization and the motivation behind it more concrete, let us consider a very simple example. Consider the manipulation of a stack by a sequence of operations composed of two kinds of unittime primitives: push, which adds a new item to the of the and the top stack, pop, which removes and returns top item on the stack. We to wish analyze the running time of a sequence of operations, each of with an composed zero or more pops followed by a push. Assume we start stack and out such can empty carry m operations. A single operation in the sequence take to m no up time units, as happens if each of the first m 1 operations performs and the last the pops operationperformsm 1 pops. However, altogether m operations can at perform most 2m pushes and pops, since there are only m pushes altogether and each pop must correspond to an earlier push. This seem too to such example may simple be useful, but stack manipulation indeed occurs in as diverse as related applications planaritytesting 14 and problems and lineartime this we shall a number of 24 string matching 18. In paper survey in which amortization is useful. Not does amortized time settings only running provide a more exact to measure the time of known but it way running algorithms, suggests that there be new efficient in an amortized rather than a worstcase may algorithms sense. As we shall such do and are more see, algorithms exist, they simpler, efficient, and more flexible than their worstcase cousins. Received by the editorsDecember 29, 1983. Thisworkwas presented at theSIAMSecond Conference on the Applications of Discrete Mathematics held at Massachusetts Institute of Technology, Cambridge, June 1983. Massachusetts, 2729, t Bell Laboratories, Murray Hill, New Jersey 07974. 306AMORTIZED ANALYSIS binary counter ‣ multipop stack ‣ dynamic table ‣ CHAPTER 17Binary counter k Goal. Increment a kbit binary counter (mod 2 ). th Representation. a = j least significant bit of counter. 17.1 Aggregate analysis 455 j 
 Counter Total value cost 
 0 00 0000 00 0 
 1 00 0000 01 1 2 00 0000 10 3 
 3 00 0000 11 4 4 00 0001 00 7 
 5 00 0001 01 8 6 00 0001 10 10 
 7 00 0001 11 11 8 00 0010 00 15 
 9 00 0010 01 16 10 00 0010 10 18 
 11 00 0010 11 19 12 00 0011 00 22 
 13 00 0011 01 23 14 00 0011 10 25 
 15 00 0011 11 26 16 00 0100 00 31 
 
 Figure17.2 An8bitbinarycounterasitsvaluegoesfrom0to16byasequenceof16INCREMENT operations. Bits that flip to achieve the next value are shaded. The running cost for flipping bits is Cost model. Number of bits flipped. shownattheright. Noticethatthetotalcostisalwayslessthantwicethetotalnumberof INCREMENT operations. 12 operations on an initially zero counter causes AŒ1 to flipbn=2c times. Similarly, bitAŒ2flipsonlyeveryfourthtime,orbn=4ctimesinasequenceofnINCREMENT i operations. In general, for i D 0;1;:::;k 1,bit AŒi flips bn=2 c times in a sequence of n INCREMENT operations on an initially zero counter. For i " k, bit AŒi does not exist, and so it cannot flip. The total number of flips in the sequence is thus k1 1 j k X X n 1 n i i 2 2 iD0 iD0 D 2n; byequation(A.6). TheworstcasetimeforasequenceofnINCREMENT operations on an initially zero counter is therefore O.n/.Theaveragecostofeachoperation, and therefore the amortized cost per operation, isO.n/=n D O.1/. A7 A6 A5 A4 A3 A2 A1 A0Binary counter k Goal. Increment a kbit binary counter (mod 2 ). th Representation. a = j least significant bit of counter. 17.1 Aggregate analysis 455 j 
 Counter Total value cost 
 0 00 0000 00 0 
 1 00 0000 01 1 2 00 0000 10 3 
 3 00 0000 11 4 4 00 0001 00 7 
 5 00 0001 01 8 6 00 0001 10 10 
 7 00 0001 11 11 8 00 0010 00 15 
 9 00 0010 01 16 10 00 0010 10 18 
 11 00 0010 11 19 12 00 0011 00 22 
 13 00 0011 01 23 14 00 0011 10 25 
 15 00 0011 11 26 16 00 0100 00 31 
 Theorem. Starting from the zero counter, a sequence of n INCREMENT Figure17.2 An8bitbinarycounterasitsvaluegoesfrom0to16byasequenceof16INCREMENT operations. Bits that flip to achieve the next value are shaded. The running cost for flipping bits is operations flips O(n k) bits. shownattheright. Noticethatthetotalcostisalwayslessthantwicethetotalnumberof INCREMENT operations. Pf. At most k bits flipped per increment. ▪ 13 operations on an initially zero counter causes AŒ1 to flipbn=2c times. Similarly, bitAŒ2flipsonlyeveryfourthtime,orbn=4ctimesinasequenceofnINCREMENT i operations. In general, for i D 0;1;:::;k 1,bit AŒi flips bn=2 c times in a sequence of n INCREMENT operations on an initially zero counter. For i " k, bit AŒi does not exist, and so it cannot flip. The total number of flips in the sequence is thus k1 1 j k X X n 1 n i i 2 2 iD0 iD0 D 2n; byequation(A.6). TheworstcasetimeforasequenceofnINCREMENT operations on an initially zero counter is therefore O.n/.Theaveragecostofeachoperation, and therefore the amortized cost per operation, isO.n/=n D O.1/. A7 A6 A5 A4 A3 A2 A1 A0Aggregate method (brute force) Aggregate method. Sum up sequence of operations, weighted by their cost. 17.1 Aggregate analysis 455 Counter Total value cost 0 00 0000 00 0 1 00 0000 01 1 2 00 0000 10 3 3 00 0000 11 4 4 00 0001 00 7 5 00 0001 01 8 6 00 0001 10 10 7 00 0001 11 11 8 00 0010 00 15 9 00 0010 01 16 10 00 0010 10 18 11 00 0010 11 19 12 00 0011 00 22 13 00 0011 01 23 14 00 0011 10 25 15 00 0011 11 26 16 00 0100 00 31 Figure17.2 An8bitbinarycounterasitsvaluegoesfrom0to16byasequenceof16INCREMENT operations. Bits that flip to achieve the next value are shaded. The running cost for flipping bits is shownattheright. Noticethatthetotalcostisalwayslessthantwicethetotalnumberof INCREMENT operations. 14 operations on an initially zero counter causes AŒ1 to flipbn=2c times. Similarly, bitAŒ2flipsonlyeveryfourthtime,orbn=4ctimesinasequenceofnINCREMENT i operations. In general, for i D 0;1;:::;k 1,bit AŒi flips bn=2 c times in a sequence of n INCREMENT operations on an initially zero counter. For i " k, bit AŒi does not exist, and so it cannot flip. The total number of flips in the sequence is thus k1 1 j k X X n 1 n i i 2 2 iD0 iD0 D 2n; byequation(A.6). TheworstcasetimeforasequenceofnINCREMENT operations on an initially zero counter is therefore O.n/.Theaveragecostofeachoperation, and therefore the amortized cost per operation, isO.n/=n D O.1/. A7 A6 A5 A4 A3 A2 A1 A0Binary counter: aggregate method Starting from the zero counter, in a sequence of n INCREMENT operations: Bit 0 flips n times. Bit 1 flips ⎣ n / 2⎦ times. Bit 2 flips ⎣ n / 4⎦ times. …
 Theorem. Starting from the zero counter, a sequence of n INCREMENT operations flips O(n) bits. Pf. j Bit j flips ⎣ n / 2⎦ times. k 1 k 1 n 1 n 1 The total number of bits flipped is
 n j j n 2 2 j j j=0 j=0 2 2 j=0 j=0 
 =2n =2n ▪ 
 
 Remark. Theorem may be false if initial counter is not zero. 15Accounting method (banker's method) Assign (potentially) different charges to each operation. th can be more or less D = data structure after i operation. i than actual cost th c = actual cost of i operation. i th ĉ = amortized cost of i operation = amount we charge operation i. i When ĉ c , we store credits in data structure D to pay for future ops;
 i i i when ĉ c , we consume credits in data structure D . i i i Initial data structure D starts with zero credits. 0 
 Key invariant. The total number of credits in the data structure ≥ 0. n n cˆ c 0 i i i=1 i=1 16Accounting method (banker's method) Assign (potentially) different charges to each operation. th can be more or less D = data structure after i operation. i than actual cost th c = actual cost of i operation. i th ĉ = amortized cost of i operation = amount we charge operation i. i When ĉ c , we store credits in data structure D to pay for future ops;
 i i i when ĉ c , we consume credits in data structure D . i i i Initial data structure D starts with zero credits. 0 
 Key invariant. The total number of credits in the data structure ≥ 0. n n 
 cˆ c 0 i i i=1 i=1 
 
 Theorem. Starting from the initial data structure D , the total actual cost of 0 any sequence of n operations is at most the sum of the amortized costs. n n cˆ c . Pf. The amortized cost of the sequence of operations is: i i ▪ i=1 i=1 
 Intuition. Measure running time in terms of credits (time = money). 17Binary counter: accounting method Credits. One credit pays for a bit flip. Invariant. Each 1 bit has one credit; each 0 bit has zero credits. 
 Accounting. Flip bit j from 0 to 1: charge two credits (use one and save one in bit j). increment 7 6 5 4 3 2 1 0 0 1 0 0 1 1 1 0 1 18Binary counter: accounting method Credits. One credit pays for a bit flip. Invariant. Each 1 bit has one credit; each 0 bit has zero credits. 
 Accounting. Flip bit j from 0 to 1: charge two credits (use one and save one in bit j). Flip bit j from 1 to 0: pay for it with the one credit saved in bit j. increment 7 6 5 4 3 2 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 19Binary counter: accounting method Credits. One credit pays for a bit flip. Invariant. Each 1 bit has one credit; each 0 bit has zero credits. 
 Accounting. Flip bit j from 0 to 1: charge two credits (use one and save one in bit j). Flip bit j from 1 to 0: pay for it with the one credit saved in bit j. 7 6 5 4 3 2 1 0 0 1 0 1 0 0 0 0 20Binary counter: accounting method Credits. One credit pays for a bit flip. Invariant. Each 1 bit has one credit; each 0 bit has zero credits. 
 Accounting. Flip bit j from 0 to 1: charge two credits (use one and save one in bit j). Flip bit j from 1 to 0: pay for it with the one credit saved in bit j. 
 
 Theorem. Starting from the zero counter, a sequence of n INCREMENT operations flips O(n) bits. 
 the rightmost 0 bit Pf. Each increment operation flips at most one 0 bit to a 1 bit
 (so the total amortized cost is at most 2n). The invariant is maintained. ⇒ number of credits in each bit ≥ 0. ▪ 21Potential method (physicist's method) Potential function. Φ(D ) maps each data structure D to a real number s.t.: i i Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each data structure D . i i 
 Actual and amortized costs. th c = actual cost of i operation. i th ĉ = c + Φ(D ) – Φ(D ) = amortized cost of i operation. i i i i–1 22Potential method (physicist's method) Potential function. Φ(D ) maps each data structure D to a real number s.t.: i i Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each data structure D . i i 
 Actual and amortized costs. th c = actual cost of i operation. i th ĉ = c + Φ(D ) – Φ(D ) = amortized cost of i operation. i i i i–1 
 Theorem. Starting from the initial data structure D , the total actual cost of 0 any sequence of n operations is at most the sum of the amortized costs. Pf. The amortized cost of the sequence of operations is: n n n n n n cˆ = (c + (D ) (D ) i i i i 1 cˆ = (c + (D ) (D ) cˆ = (c + (D ) (D ) i i i i 1 i i i i 1 i=1 i=1 i=1 i=1 i=1 i=1 n n n = c + (D ) (D ) i n 0 = c + (D ) (D ) = c + (D ) (D ) i n 0 i n 0 i=1 i=1 i=1 n n n c i c c i i ▪ i=1 i=1 i=1 23Binary counter: potential method Potential function. Let Φ(D) = number of 1 bits in the binary counter D. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i increment 7 6 5 4 3 2 1 0 0 1 0 0 1 1 1 0 1 24Binary counter: potential method Potential function. Let Φ(D) = number of 1 bits in the binary counter D. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i increment 7 6 5 4 3 2 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 25Binary counter: potential method Potential function. Let Φ(D) = number of 1 bits in the binary counter D. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i 7 6 5 4 3 2 1 0 0 1 0 1 0 0 0 0 26Binary counter: potential method Potential function. Let Φ(D) = number of 1 bits in the binary counter D. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i 
 
 Theorem. Starting from the zero counter, a sequence of n INCREMENT operations flips O(n) bits. Pf. th Suppose that the i increment operation flips t bits from 1 to 0. i operation sets one bit to 1 (unless counter resets to zero) The actual cost c ≤ t + 1. i i The amortized cost ĉ = c +Φ(D ) – Φ(D ) i i i i–1 ≤ c + 1 – t i i ≤ 2. ▪ 27Famous potential functions Fibonacci heaps. (H)=2trees(H)+2marks(H) 
 Splay trees. (T)= log size(x) 2 x T 
 
 (L)= 2 inversions(L,L ) Movetofront. 
 (f)= height(v) Preflow–push. v :excess(v)0 
 
 Redblack trees. (T)= w(x) x T 0B7 xBb`2/ 1B7 xBbFH+M/bMQ`2/BH/`2M+ w(x)= 0B7 xBbFH+M/bQM2`2/BH/+ 2B7 xBbFH+M/bQri`2/BH/`2M+ 28AMORTIZED ANALYSIS binary counter ‣ multipop stack ‣ dynamic table ‣ SECTION 17.4Multipop stack Goal. Support operations on a set of elements: PUSH(S, x): push object x onto stack S. POP(S): remove and return the mostrecently added object. MULTIPOP(S, k): remove the mostrecently added k objects. 
 
 
 
 MULTIPOP (S, k) 
 FOR i = 1 TO k 
 POP (S). 
 
 
 
 
 Exceptions. We assume POP throws an exception if stack is empty. 30Multipop stack Goal. Support operations on a set of elements: PUSH(S, x): push object x onto stack S. POP(S): remove and return the mostrecently added object. MULTIPOP(S, k): remove the mostrecently added k objects. 
 
 Theorem. Starting from an empty stack, any intermixed sequence of n
 2 PUSH, POP, and MULTIPOP operations takes O(n ) time. Pf. overly pessimistic upper bound Use a singlylinked list. PoP and PUSH take O(1) time each. MULTIPOP takes O(n) time. ▪ top 1 4 1 3 ● ● ● ● ● 31Multipop stack: aggregate method Goal. Support operations on a set of elements: PUSH(S, x): push object x onto stack S. POP(S): remove and return the mostrecently added object. MULTIPOP(S, k): remove the mostrecently added k objects. 
 
 Theorem. Starting from an empty stack, any intermixed sequence of n
 PUSH, POP, and MULTIPOP operations takes O(n) time. Pf. An object is popped at most once for each time it is pushed onto stack. There are ≤ n PUSH operations. Thus, there are ≤ n POP operations
 (including those made within MULTIPOP). ▪ 32Multipop stack: accounting method Credits. One credit pays for a push or pop.
 Accounting. PUSH(S, x): charge two credits. use one credit to pay for pushing x now store one credit to pay for popping x at some point in the future No other operation is charged a credit. 
 
 Theorem. Starting from an empty stack, any intermixed sequence of n
 PUSH, POP, and MULTIPOP operations takes O(n) time. 
 Pf. The algorithm maintains the invariant that every object remaining on the stack has 1 credit ⇒ number of credits in data structure ≥ 0. ▪ 33Multipop stack: potential method Potential function. Let Φ(D) = number of objects currently on the stack. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i 
 Theorem. Starting from an empty stack, any intermixed sequence of n
 PUSH, POP, and MULTIPOP operations takes O(n) time. 
 Pf. Case 1: push th Suppose that the i operation is a PUSH. The actual cost c = 1. i The amortized cost ĉ = c +Φ(D ) – Φ(D ) = 1 + 1 = 2. i i i i–1 34Multipop stack: potential method Potential function. Let Φ(D) = number of objects currently on the stack. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i 
 Theorem. Starting from an empty stack, any intermixed sequence of n
 PUSH, POP, and MULTIPOP operations takes O(n) time. 
 Pf. Case 2: pop th Suppose that the i operation is a POP. The actual cost c = 1. i The amortized cost ĉ = c +Φ(D ) – Φ(D ) = 1 – 1 = 0. i i i i–1 35Multipop stack: potential method Potential function. Let Φ(D) = number of objects currently on the stack. Φ(D ) = 0. 0 Φ(D ) ≥ 0 for each D . i i 
 Theorem. Starting from an empty stack, any intermixed sequence of n
 PUSH, POP, and MULTIPOP operations takes O(n) time. 
 Pf. Case 3: multipop th Suppose that the i operation is a MULTIPOP of k objects. The actual cost c = k. i The amortized cost ĉ = c +Φ(D ) – Φ(D ) = k – k = 0. ▪ i i i i–1 36AMORTIZED ANALYSIS binary counter ‣ multipop stack ‣ dynamic table ‣ SECTION 17.4Dynamic table Goal. Store items in a table (e.g., for hash table, binary heap). Two operations: INSERT and DELETE. too many items inserted ⇒ expand table. too many items deleted ⇒ contract table. Requirement: if table contains m items, then space = Θ(m). 
 
 Theorem. Starting from an empty dynamic table, any intermixed sequence 2 of n INSERT and DELETE operations takes O(n ) time. 
 overly pessimistic upper bound Pf. A single INSERT or DELETE takes O(n) time. ▪ 38Dynamic table: insert only Initialize empty table of capacity 1. INSERT: if table is full, first copy all items to a table of twice the capacity. old new insert 
 copy insert 
 capacity capacity cost cost 
 1 1 1 1 – 
 2 1 2 1 1 
 3 2 4 1 2 
 4 4 4 1 – 
 5 4 8 1 4 
 6 8 8 1 – 
 7 8 8 1 – 
 8 8 8 1 – 9 8 16 1 8 
 ⋮ ⋮ ⋮ ⋮ ⋮ 
 
 Cost model. Number of items written (due to insertion or copy). 39Dynamic table: insert only (aggregate method) Theorem. via aggregate method Starting from an empty dynamic table,
 any sequence of n INSERT operations takes O(n) time. 
 th Pf. Let c denote the cost of the i insertion. i 
 iB7 i 1BbM2t+i2`TrQQ7k 
 c = i 1Qi2`rBb2 
 
 Starting from empty table, the cost of a sequence of n INSERT operations is: lgn lgn n n lgn n j j c n + 2 c n + 2 j i i c n + 2 i i=1 j=0 i=1 j=0 i=1 j=0 n+2n n+2n n+2n =3n =3n =3n ▪ 40Dynamic table: insert only (accounting method) WLOG, can assume the table fills from left to right. 1 2 3 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 41Dynamic table: insert only (accounting method) Accounting. INSERT: charge 3 credits (use 1 credit to insert; save 2 with new item). 
 
 Theorem. via accounting method Starting from an empty dynamic table,
 any sequence of n INSERT operations takes O(n) time. 
 Pf. The algorithm maintains the invariant that there are 2 credits with each item in right half of table. When table doubles, onehalf of the items in the table have 2 credits. This pays for the work needed to double the table. ▪ 42Dynamic table: insert only (potential method) Theorem. via potential method Starting from an empty dynamic table,
 any sequence of n INSERT operations takes O(n) time. 
 Pf. Let Φ(D ) = 2 size(D ) – capacity(D ). i i i number of capacity of elements array 1 2 3 4 5 6 43Dynamic table: insert only (potential method) Theorem. via potential method Starting from an empty dynamic table,
 any sequence of n INSERT operations takes O(n) time. 
 Pf. Let Φ(D ) = 2 size(D ) – capacity(D ). i i i 
 number of capacity of 
 elements array 
 Case 1. does not trigger expansion size(D ) ≤ capacity(D ). i i–1 Actual cost c = 1. i Φ(D ) – Φ(D ) = 2. i i–1 Amortized costs ĉ = c + Φ(D ) – Φ(D ) = 1 + 2 = 3. i i i i–1 
 Case 2. triggers expansion size(D ) = 1 + capacity(D ). i i–1 Actual cost c = 1 + capacity(D ). i i–1 Φ(D ) – Φ(D ) = 2 – capacity(D ) + capacity(D ) = 2 – capacity(D ). i i–1 i i–1 i–1 Amortized costs ĉ = c + Φ(D ) – Φ(D ) = 1 + 2 = 3. ▪ i i i i–1 44Dynamic table: doubling and halving Thrashing. Initialize table to be of fixed capacity, say 1. INSERT: if table is full, expand to a table of twice the capacity. DELETE: if table is ½full, contract to a table of half the capacity. 
 
 Efficient solution. Initialize table to be of fixed capacity, say 1. INSERT: if table is full, expand to a table of twice the capacity. DELETE: if table is ¼full, contract to a table of half the capacity. 
 
 Memory usage. A dynamic table uses O(n) memory to store n items. Pf. Table is always at least ¼full (provided it is not empty). ▪ 45Dynamic table: insert and delete (accounting method) insert 1 2 3 4 5 6 7 8 9 10 11 12 delete 1 2 3 4 5 6 7 8 9 10 11 12 resize and delete 1 2 3 4 46Dynamic table: insert and delete (accounting method) Accounting. INSERT: charge 3 credits (1 credit for insert; save 2 with new item). DELETE: charge 2 credits (1 credit to delete, save 1 in emptied slot). 
 discard any existing credits 
 Theorem. via accounting method Starting from an empty dynamic table,
 any intermixed sequence of n INSERT and DELETE operations takes O(n) time. 
 Pf. The algorithm maintains the invariant that there are 2 credits with each item in the right half of table; 1 credit with each empty slot in the left half. When table doubles, each item in right half of table has 2 credits. When table halves, each empty slot in left half of table has 1 credit. ▪ 47Dynamic table: insert and delete (potential method) Theorem. via potential method Starting from an empty dynamic table,
 any intermixed sequence of n INSERT and DELETE operations takes O(n) time. 
 Pf sketch. Let α(D ) = size(D ) / capacity(D ).
 i i i 2size(D ) capacity(D )B7 (D ) 1/2 i i i Define
 (D)= i 1 capacity(D ) size(D )B7 (D ) 1/2 i i i 2 
 When α(D) = 1/2, Φ(D) = 0. zero potential after resizing When α(D) = 1, Φ(D) = size(D ). can pay for expansion i When α(D) = 1/4, Φ(D) = size(D ). can pay for contraction
 i ... 48