Consider a counter which counts distance by feet, yards, furlongs and miles. 1 yard = 3...

Transcribed Image Text:

Consider a counter which counts distance by feet, yards, furlongs and miles. 1 yard = 3 feet, 1 furlong = 220 yards and 1 mile = 8 furlongs. When counter shows ABCD - it means we have travelled A miles, B furlongs, C yards and D feet. Where B < 8, C < 220 and D < 3. The counter increments one feet at a time. The cost of a particular increment is how many of the values A, B, C or D increment. Thus, the worst case cost for an increment can be 4. However, amortized cost of increment is much smaller. What is the amortized cost of such an increment (you may use aggregate method for this part)? Design a potential function which achieves this amortized cost. Note that amortized cost is to be measured here as a precise real number rather than O(1). Consider a counter which counts distance by feet, yards, furlongs and miles. 1 yard = 3 feet, 1 furlong = 220 yards and 1 mile = 8 furlongs. When counter shows ABCD - it means we have travelled A miles, B furlongs, C yards and D feet. Where B < 8, C < 220 and D < 3. The counter increments one feet at a time. The cost of a particular increment is how many of the values A, B, C or D increment. Thus, the worst case cost for an increment can be 4. However, amortized cost of increment is much smaller. What is the amortized cost of such an increment (you may use aggregate method for this part)? Design a potential function which achieves this amortized cost. Note that amortized cost is to be measured here as a precise real number rather than O(1).

Answer rating: 100% (QA)

To determine the amortized cost of an increment operation in this scenario we can use the aggregate ... View the full answer