CmSc 250 Intro to Algorithms
Homework 06 due 02/26
1. Design a class TwoStacks that implements two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The push and pop operations should run in O(1) time. Explain your idea about the implementation and then write down the private variables of the class, the constructor (s) and the methods push, pop, and isEmpty for each stack. Note that for each stack you will need separate pop, push etc methods. You will need a method isFull returning true if the array is full. Implement the class. Implement a test class that allows to test the methods of the TwoStacks class. In the test class, provide a menu that lists the methods to be tested.
2. Consider the following two methods
public static int methodOne(int [] array)
{
int i, j;
int n = array.length;
for(i = 0; i < n ; i++)
{
if (array[i] == 0)
{
for (j = i; j < n-1; j ++)
array[j] = array[j+1];
n = n-1;
i--;
}
}
return n;
}
/* ------*/
public static int methodOne(int [] array)
{
int i, j;
int n = array.length;
i = 0;
while (array[i]!= 0 & i < n) i++;
if (i == n);
else {
for (j = i + 1;j < n; j++){
if (a[j] !=0) {
a[i] = a[j];
i = i+1;
}
}
n = i;
}
return n;
}
Explain what these methods do. What happens with the array after it has been processed by the methods, what is the meaning of the returned value? Analyze the complexity of each method in terms of BigOh.
3. Trace the buildHeap method applied to the following array
75, 6, 24, 102, 27, 15, 18, 99, 72, 25, 8, 84
Give the contents of the array after each percolateDown operation. One percolateDown operation will rearrange the nodes from the current node down to the bottom of the tree