1. Consider amortized cost for the scenario where we have a stack such that: A...

 

Transcribed Image Text:

1. Consider amortized cost for the scenario where we have a stack such that: • A pop costs 1. . A push costs 1, not counting any allocation that may be necessary. • Re-allocation costs the new size. This cost includes copying the contents of the old stack. Assume we start with 0 bytes allocated and when we re-allocate we multiply the length by a € Z where a ≥ 2 except for the very first re-allocation which goes from 0 to 1. Define: f(a) - a² + a-1 a - 1 (a) Use the aggregate method to prove that in the worst case with n operations the amortized [25 pts] cost AC (n) of each stack operation satisfies AC(n) ≤ f(a). (b) Prove mathematically that this expression is minimum when a = 2. [15 pts] 1. Consider amortized cost for the scenario where we have a stack such that: • A pop costs 1. . A push costs 1, not counting any allocation that may be necessary. • Re-allocation costs the new size. This cost includes copying the contents of the old stack. Assume we start with 0 bytes allocated and when we re-allocate we multiply the length by a € Z where a ≥ 2 except for the very first re-allocation which goes from 0 to 1. Define: f(a) - a² + a-1 a - 1 (a) Use the aggregate method to prove that in the worst case with n operations the amortized [25 pts] cost AC (n) of each stack operation satisfies AC(n) ≤ f(a). (b) Prove mathematically that this expression is minimum when a = 2. [15 pts] 1. Consider amortized cost for the scenario where we have a stack such that: • A pop costs 1. . A push costs 1, not counting any allocation that may be necessary. • Re-allocation costs the new size. This cost includes copying the contents of the old stack. Assume we start with 0 bytes allocated and when we re-allocate we multiply the length by a € Z where a ≥ 2 except for the very first re-allocation which goes from 0 to 1. Define: f(a) - a² + a-1 a - 1 (a) Use the aggregate method to prove that in the worst case with n operations the amortized [25 pts] cost AC (n) of each stack operation satisfies AC(n) ≤ f(a). (b) Prove mathematically that this expression is minimum when a = 2. [15 pts] 1. Consider amortized cost for the scenario where we have a stack such that: • A pop costs 1. . A push costs 1, not counting any allocation that may be necessary. • Re-allocation costs the new size. This cost includes copying the contents of the old stack. Assume we start with 0 bytes allocated and when we re-allocate we multiply the length by a € Z where a ≥ 2 except for the very first re-allocation which goes from 0 to 1. Define: f(a) - a² + a-1 a - 1 (a) Use the aggregate method to prove that in the worst case with n operations the amortized [25 pts] cost AC (n) of each stack operation satisfies AC(n) ≤ f(a). (b) Prove mathematically that this expression is minimum when a = 2. [15 pts]

Answer rating: 100% (QA)

To address this question lets start by breaking it down into two parts as the question has two separate sections part a and part b Part a Aggregate Method for Amortized Cost We are given a stack with ... View the full answer