Question

1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A.

1. What is the best-case running time of Algorithm X?
2. What is the worst-case running time of Algorithm X?

2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm outputs two integers: the initial and final indices of the longest subarray.

1. Give the algorithm pseudocode.
2. Implement your algorithm and test it using java.
3. Justify your big-Oh.

3. Suppose you are given a sorted array, A, of n distinct integers in the range from 1 to n+1, so there is exactly one integer in this range missing from A. Give an O(log n)- time algorithm for finding the integer in this range that is not in A. Hint: the algorithm resembles binary search.

1. Give the algorithm pseudocode.
2. Implement your algorithm and test it using java.
3. Justify your big-Oh.

4. Consider an implementation of a stack ADT using an extendable array, but instead of doubling the size, when an array of size N is full, you create a new array of size N + 4. Assume you start with an array of size 0 (i.e., the first push is a special push. Note: A special push is the push when I need to create a new array and copy the previous elements to the new array plus the element that I am trying to insert):

a) What is the cost of the 5th push?

b) how many normal push can be performed between any two special push?

c) what is the cost of the i-th special push?

d) what is the overall cost of performing n push (give the exact formula as well   as the big-Oh characterization)?

Answer 1

1) Given that for any element "B", best time i.e. O(log n) (as given)is achieved when B is odd and if B is even O(n) is achieved

Now, best case running time of algorithm would be when each element would recieve its best case time i.e. if each element E is odd. Hence Complexity of Algorithm X = n * best complexity of each element = n*O(log n) = O (n*log n)

Similarly,

Worst case running time of Algorithm X = n * worst complexity of each element = n * O(n) = O(n^2)

********************************************************************************************************************

2)

void longest(int a[],int n)
{
int i,k1,k2,l1,l2,pos1,pos2;
k1=k2=l1=l2=1;
pos1=pos2=0;
for(i=1;i<n;i++)
{
if(a[i]>=a[i-1])
{
k1++;
k2=1;
if(k1>l1)
{
l1=k1;
pos1=i;
}
}
else
{
k2++;
k1=1;
if(k2>l2)
{
l2=k2;
pos2=i;
}
}
}
int ans,p;
if(l1>l2){
ans=pos1;
p=l1;}
else{
ans=pos2;
p=l2;}
printf("%d %d",ans-p+1,ans);
}
int main()
{

int n,i;
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);
longest(a,n);
}

As we can easily see that we can iterate over the entire array of length n and performing constant no of operations with in the for loop.So the time complexity is O(n).

********************************************************************************************************************

3)If the array is already sorted, then what we do is, we traverse the entire array. This would give a linear time complexity of ( O ( n ) ).We can use binary search method in order to find the missing element in logarithmic time complexity ( O ( log n ) ), as is required here.On removing an element, obviously, the condition

a[i] = I;

will not be valid anymore.

So, we move onto the next step to determine the missing element.

For this, we check the middle element. This helps determine if it satisfies the mentioned condition.

If a[mid] > mid; check the left half of the array

Else

Check the right half of the array

Code:

int find_missing_element (int a [], int n)

{

    int low = 0, mid, high = n-1;

    while (low <= high)

    {

        mid = (low + high)/2;

        if (a[mid] > mid)

        {

            high = mid-1;

        }

        else

        {

            low = mid+1;

        }

    }

    return low;

}

********************************************************************************************************************

4)a) Array size = 0.And we are given if array is full then create new array of size N + 4.

Create new array 0 + 4 =4 .Now we consider array of size 4 can push only 4 elements in an array.

Now for pushing 5th element in a stack. We follow the rule we ceate a new array of size N + 4.

i.e 4 + 4 = 8.Then shifting all 4 elements in the stack and the pushing 5th element into the stack merging of elements from one array to other takes O(n) time and pushing element is take O(1) time because of element push at the top of stack.Total time takened to push 5th element in a stack is O(n) + O(1) = O(n).

b)As we considering array size of 4 can hold 4 values.4Then there are 3 normal pushes which are between two special pushes.If we consider 1st push is a special push. Then 2nd,3rd and 4th push are available after that array is full and another push will be a special push.So there are 3 normal pushes 2nd,3rd and 4th in between the two special pushes.(i.e 1st and 5th).

c) As we already find our 5th push which is a special push costs O(n).Then it is clear every ith special push takes O(n) time. where n is the number of element presents in the stack before pushing new element. (because of merging in new array).

d)if we done any normal push the we only takes O(1) time.But when we done special push it takes O(n) time because of merging of elements from the old array to the new array and after that push new elemnt.So if frequency of our push is less than or equall to the stack size or array size then it takes O(1) time to push n elemnt in a stack.And if frequency increase with the size of stack then it takes O(n) time to push n elements in a stack.

********************************************************************************************************************

note:-I have writtin a general psuedocode you can easily implement in java

#################################################################################

In case of any doubt do ask in the comment section