Please answer clearly as required.

Problem 1 : In class, we used amortized analysis to study the extensible array problem. An extensible array is a type of data structure that is like an array, but is resized when it becomes full. The extensible array supports only one operation: "insert". It works as follows: Initially, the array has space for just one element.

Suppose that the array is currently of size k and is full. Then if you attempt to insert an element, the OS will allocate new memory of size 2k, and all k elements currently in the array will be copied to the new location and then the new element will be written.

In class, we assumed that writing or copying an element cost $1, and allocating memory was free. Suppose now that writing or copying an element still costs $1, but now we must also pay $1 for each unit of memory that is allocated. (In other words, if we allocate 2k units of memory, we must pay $2k.)

Perform an amortized analysis of the running time of n insert operations on an extensible array, under the new cost model. State your answer in terms of the average cost per operation, in dollars (that is, do not use big-O notation).

Problem 2 : Suppose that we have a stack whose size is not allowed to exceed K (for instance, if K 10, then we are not allowed to have more than 10 elements on the stack at any time).

If you try to Push an element onto a stack that is already full, then nothing happens. Suppose that after every K operations, we automatically make a copy of the stack for back-up purposes.

(Note the stack may or may not be full at this point.) Suppose that Push and Pop each cost $1 (including if you try to Push an element onto an already-full stack).

Suppose that copying the stack costs SC, where C is the number of elements currently on the stack. Perform an amortized analysis of the running time of n operations. State your answer in terms of the average cost per operation, in dollars (that is, do not use big-O notation).