Problem 3. (15 marks) Once a Push() call is invoked on a full stack (stack.size
ID: 3737062 • Letter: P
Question
Problem 3. (15 marks) Once a Push() call is invoked on a full stack (stack.size = stack.capacity), we increase the capacity of a stack (or a queue, or a hash-table) using IncreaseCapacity():
1. Allocate a new array with 2 x stack.capacitycells- ;
2. Copy all items from the original array to the new array, delete the old array.
Analogously to this, once stack.size is small in comparison to stack.capacity, we can decrease the capacity and clear some memory using DecreaseCapacity():
1. Allocate a new array with stack.capacity/2 cells;
2. Copy all items from the original array to the new array, delete the old array.
(Note that both IncreaseCapacity() and DecreaseCapacity() run in Theta (n)-time .)
a. (5 marks) Prove that invoking DecreaseCapacity() whenever stack.size = stack.capacity/2 is unwise. That is, show that starting with stack.size = 0, there exists a sequence of n Push()/Pop() instructions whose amortized cost is Omega (n) .
b. (10 marks) Prove that invoking DecreaseCapacity() whenever stack.size = stack.capacity/3 maintains constant amortized cost. That is, show that any sequence of n Push()/Pop() instructions has amortized cost of O(1). You may assume stack.capacity = 1 initially.( Hint: Call an instruction heavy if it invokes either IncreaseCapacity() or DecreaseCapacity(); and call it light otherwise. Light instructions always take O(1). Your argument should probably begin by showing that between any two heavy instructions there have to be at least small pcdot m light instructions (by considering all 4 possible cases), where m denotes the capacity of the stack between the two heavy instructions and 0 < p < 1 is a constant you need to find. Then use this claim to prove, by induction, that T(n) defined as the worst-case cost of a sequence of n Push()/PoP() instructions is in O(n).)
Explanation / Answer
public class StackResizeArray <T> {
T[] content;
int size;
public static void main(String[] args) {
StackResizeArray stack = new StackResizeArray();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.toString());
try {
stack.pop();
stack.pop();
} catch (Exception e) {
e.printStackTrace(); //To change body of catch statement use File | Settings | File Templates.
}
System.out.println(stack.toString());
}
public StackResizeArray(){
this.content = (T[]) new Object[1];
this.size = 0;
}
/*
* This is a method which resizes the capacity of the array of the stack
* @author Gong Li
* @param capacity the expected size of the array in this stack
* */
private void resize(int capacity){
T[] copy = (T[]) new Object[capacity];
for (int i = 0; i < size; i ++){
copy[i] = this.content[i];
}
this.content = copy;
}
public void push(T item){
if (this.size == content.length)
resize(2*this.size);
content[size ++] = item;
}
public T pop() throws Exception {
if (size == 0) throw new Exception("This stack is empty!");
T item = content[--size];
content[size] = null;
if (size > 0 && size == content.length / 4)
resize(content.length / 2);
return item;
}
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
for (int i = 0; i < size; i ++){
T t = content[i];
sb.append(t.toString()+" ");
}
return sb.toString();
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.