Basics of data structures ppt

asymptotic notations in data structures ppt and data structures algorithms ppt
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
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/kleinberg-tardos 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, max-flow, ... 
 Dynamic problems. Given a sequence of operations (given one at a time), produce a sequence of outputs. Ex. Stack, queue, priority queue, symbol table, union-find, …. 
 Algorithm. Step-by-step 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/kleinberg-tardos Last updated on 1/24/17 11:31 AMAmortized analysis Worst-case analysis. Determine worst-case 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 worst-case 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. Move-to-front list updating. Push-relabel algorithm for max flow. Path compression for disjoint-set union. Structural modifications to red-black 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 "self-adjusting" 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 worst-case in which we sum the worst-case 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 average-case 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 (worst-case) 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 unit-time 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 planarity-testing 14 and problems and linear-time 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 worst-case may algorithms sense. As we shall such do and are more see, algorithms exist, they simpler, efficient, and more flexible than their worst-case 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, 27-29, t Bell Laboratories, Murray Hill, New Jersey 07974. 306AMORTIZED ANALYSIS binary counter ‣ multipop stack ‣ dynamic table ‣ CHAPTER 17Binary counter k Goal. Increment a k-bit 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 An8-bitbinarycounterasitsvaluegoesfrom0to16byasequenceof16INCREMENT 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). Theworst-casetimeforasequenceofnINCREMENT 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 k-bit 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 An8-bitbinarycounterasitsvaluegoesfrom0to16byasequenceof16INCREMENT 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). Theworst-casetimeforasequenceofnINCREMENT 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 An8-bitbinarycounterasitsvaluegoesfrom0to16byasequenceof16INCREMENT 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). Theworst-casetimeforasequenceofnINCREMENT 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 20