MCS-375 Homework 6 (Fall 2011)

For this 12-point assignment, you will investigate two alternative implementations of a ScopedMap class, which I have attached as the files BadScopedMap.py and GoodScopedMap.py. Aside from performance, all methods of the two classes ought to behave identically. (If you find an incompatibility, please let me know there is a bug in my code.)

Some of you may be familiar with a slight variant of this class from MCS-287. Whether or not you are, I don't intend for you to spend a lot of time figuring out how the class would be used or how it works internally. So please don't be shy about asking questions on these topics.

For this assignment, you may use the following simplified cost model for Python:

Each use of square brackets or curly braces costs one unit.
Each use of the len function costs one unit.
Each use of the in operator as a boolean test of membership costs one unit.
Each use of the in operator to control a for loop costs one unit per iteration.
Each use of the append, pop, or get method costs one unit.
The phrase "each use" means number of times executed; take loops and conditionals into account.
If one ScopedMap method uses another, the indirect costs need to be included.
All other operations are free.

Analyze the implementations as follows:

For each method in BadScopedMap, provide a tight, non-asymptotic upper bound on the cost. Examples of the appropriate form of answer would be 7, 3n, and 2n + 5. If you give a formula involving n, specify what n is. For example, it might be the size of some particular data structure.
Consider the following sequence of 2n operations: initialize a new BadScopedMap, repeat enterScope n − 1 times, then repeat retrieve n times. Using your answers from the prior part, what is the total upper bound on the cost of this sequence?
In the preceding scenario, what is the actual (not upper-bound) total cost of the sequence?
For each method in GoodScopedMap, provide a tight, non-asymptotic upper bound on the cost. Examples of the appropriate form of answer would be 7, 3n, and 2n + 5. If you give a formula involving n, specify what n is. For example, it might be the size of some particular data structure.
Suppose we define a potential function on the GoodScopedMap as some positive multiple, C, of the total number of key/value pairs in all the dictionaries in scopes. For each method, provide a tight, non-asymptotic upper bound on how much that method changes the potential of the data structure. (If the potential might increase, your bound will be positive. If the potential decreases, your bound will be negative. If the potential remains unchanged, your bound will be 0.) Some of your answers may be formulas involving both C and n. When you use n, specify what it is. For example, it might be the size of some particular data structure.
For each method in GoodScopedMap, write a formula that is a tight, non-asymptotic upper bound on the amortized cost. This is simply the sum of your formulas from the preceding two problems, one for the cost and the other for the change in potential. Some of your answers may be formulas involving both C and n. When you use n, specify what it is. For example, it might be the size of some particular data structure.
Choose a positive value for C such that each of your amortized-cost formulas from the preceding problem evaluates to a constant upper bound. Indicate what your value of C is and what the constant upper bound is on each method's amortized cost.