Data Representation Methods

Data Representation Methods

Amortized Complexity Aggregate method. Accounting method. Potential function method. Potential Function P() P(i) = amortizedCost(i) actualCost(i) + P(i 1) (P(i) P(i 1)) = (amortizedCost(i) actualCost(i)) P(n) P(0) = (amortizedCost(i) actualCost(i)) P(n) P(0) >= 0

When P(0) = 0, P(i) is the amount by which the first i operations have been over charged. Potential Function Example a=x+((a+b actual cost 1 1 1 1 1 11 1 1 amortized cost 2 2 2 2 2 22 2 2 potential 1 2 3 4 5 67 8 9 )*c+d )+y; 511117117

222222222 6 7 8 9 10 5 6 7 2 Potential = stack size except at end. Accounting Method Guess the amortized cost. Show that P(n) P(0) >= 0. Accounting Method Example create an empty stack;

for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol(); Guess that amortized complexity of processNextSymbol is 2. Start with P(0) = 0. Can show that P(i) >= number of elements on stack after ith symbol is processed. Accounting Method Example a=x+((a+b

actual cost 1 1 1 1 1 11 1 1 amortized cost 2 2 2 2 2 22 2 2 potential 1 2 3 4 5 67 8 9 )*c+d )+y; 511117117 222222222 6 7 8 9 10 5 6 7 2 Potential >= number of symbols on stack. Therefore, P(i) >= 0 for all i.

In particular, P(n) >= 0. Potential Method Guess a suitable potential function for which P(n) P(0) >= 0 for all n. Derive amortized cost of ith operation using P = P(i) P(i1) = amortized cost actual cost amortized cost = actual cost + P Potential Method Example

create an empty stack; for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol(); Guess that the potential function is P(i) = number of elements on stack after ith symbol is processed (exception is P(n) = 2). P(0) = 0 and P(i) P(0) >= 0 for all i. ith Symbol Is Not ) or ; Actual cost of processNextSymbol is 1.

Number of elements on stack increases by 1. P = P(i) P(i1) = 1. amortized cost = actual cost + P =1+1=2 ith Symbol Is ) Actual cost of processNextSymbol is #unstacked + 1. Number of elements on stack decreases by #unstacked 1. P = P(i) P(i1) = 1 #unstacked.

amortized cost = actual cost + P = #unstacked + 1 + (1 #unstacked) =2 ith Symbol Is ; Actual cost of processNextSymbol is #unstacked = P(n1). Number of elements on stack decreases by P(n1). P = P(n) P(n1) = 2 P(n1).

amortized cost = actual cost + P = P(n1) + (2 P(n1)) =2 Binary Counter n-bit counter Cost of incrementing counter is number of bits that change. Cost of 001011 => 001100 is 3. Counter starts at 0. What is the cost of incrementing the counter

m times? Worst-Case Method Worst-case cost of an increment is n. Cost of 011111 => 100000 is 6. So, the cost of m increments is at most mn. Aggregate Method 00000 counter Each increment changes bit 0 (i.e., the right

most bit). Exactly floor(m/2) increments change bit 1 (i.e., second bit from right). Exactly floor(m/4) increments change bit 2. Aggregate Method 00000 counter Exactly floor(m/8) increments change bit 3. So, the cost of m increments is m + floor(m/2) + floor(m/4) + .... < 2m

Amortized cost of an increment is 2m/m = 2. Accounting Method Guess that the amortized cost of an increment is 2. Now show that P(m) P(0) >= 0 for all m. 1st increment: one unit of amortized cost is used to pay for the change in bit 0 from 0 to 1. the other unit remains as a credit on bit 0 and is used later to pay for the time when bit 0 changes from 1 to 0.

bits credits 00000 00000 00001 00001 2nd Increment. bits

credits 00001 00001 00010 00010 one unit of amortized cost is used to pay for the change in bit 1 from 0 to 1 the other unit remains as a credit on bit 1 and is used

later to pay for the time when bit 1 changes from 1 to 0 the change in bit 0 from 1 to 0 is paid for by the credit on bit 0 3rd Increment. bits credits 00010 00010

00011 00011 one unit of amortized cost is used to pay for the change in bit 0 from 0 to 1 the other unit remains as a credit on bit 0 and is used later to pay for the time when bit 1 changes from 1 to 0 4th Increment.

bits credits 00011 00011 00100 00100 one unit of amortized cost is used to pay for the change in bit 2 from 0 to 1

the other unit remains as a credit on bit 2 and is used later to pay for the time when bit 2 changes from 1 to 0 the change in bits 0 and 1 from 1 to 0 is paid for by the credits on these bits Accounting Method P(m) P(0) = (amortizedCost(i) actualCost(i)) = amount by which the first m increments have been over charged = number of credits

= number of 1s in binary rep. of m >= 0 Potential Method Guess a suitable potential function for which P(n) P(0) >= 0 for all n. Derive amortized cost of ith operation using P = P(i) P(i1) = amortized cost actual cost amortized cost = actual cost + P

Potential Method Guess P(i) = number of 1s in counter after ith increment. P(i) >= 0 and P(0) = 0. Let q = # of 1s at right end of counter just before ith increment (01001111 => q = 4). Actual cost of ith increment is 1+q. P = P(i) P(i 1) = 1 q (0100111 => 0101000) amortized cost = actual cost + P = 1+q + (1 q) = 2

Recently Viewed Presentations

  • Haas Career Management Center Database IEOR 115 Ken

    Haas Career Management Center Database IEOR 115 Ken

    Li | AdibKashem. IEOR 115. Ken Goldberg. Final Presentation. December, 10, 2011. Overview. Haas School of Business Career Management Group. Provides candidates access to employers. Organizes on campus career events. Handles 1000+ electronic job postings per year.
  • Thermodynamics - CMU

    Thermodynamics - CMU

    Heat Capacity (denoted by letter "C") Measurement of the amount of heat required to change a substance's temperature by a certain amount. Objects differ in their abilities to transform heat transfer into temperature change. C = q. DT. C= Heat...
  • 852 Talking Points - HCI

    852 Talking Points - HCI

    Experience a wide variety of leadership styles . Identify and understand key traits that impact the organization's performance. Determine strategies for implementing organizational change and transformation in the Navy acquisition and other cross-cultural environments. Learn how to set attainable goals...
  • Teaching Writing Using the Writing Process

    Teaching Writing Using the Writing Process

    TEACHING WRITING USING THE WRITING PROCESS ... variety of aspects of each stage of the writing process. 0.3 Teachers develop and implement an efficient classroom management system for supporting each student in the various stages of the writing process. 0.4...
  • Topic: Ecosystem Stability

    Topic: Ecosystem Stability

    What are the 2 main components of a stable ecosystem? 2. Summarize the difference between the two. 3. What is the key to maintaining a stable ecosystem? 4. What examples of biodiversity can you come up with? Types of Biodiversity.
  • Problem Management Training - Oklahoma

    Problem Management Training - Oklahoma

    The typical sources for problems are the Service Desk, Service Provider Groups, and proactive problem management through Quality Assurance. Office of State Finance Contents Process * * Process Flow Process Flow - Identification Anyone within OSF / ISD can request...
  • 4 - Office 365 Fundamentals Deploying

    4 - Office 365 Fundamentals Deploying

    User migration (PST import) or IMAP Migration. New mail file. Deploy Experience - what's added. 6/3/2014. Microsoft Office365. Identity. ... MICROSOFT MAKES NO WARRANTIES, EXPRESS, IMPLIED OR STATUTORY, AS TO THE INFORMATION IN THIS PRESENTATION. 6/3/2014 3:45 PM
  • USCOM Hemodynamic Measures- A rational approach to improve ...

    USCOM Hemodynamic Measures- A rational approach to improve ...

    USCOM Hemodynamic Measures A rational approach to improve outcomes