Question

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

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)?

Homework Answers

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

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1.A stack implemented with an array has what performance? Select one: a. O(n3) b. O(n log...
1.A stack implemented with an array has what performance? Select one: a. O(n3) b. O(n log n) c. O(n) d. O(n2) 2. A stack uses the first in first out insertion and deletion method. Select one: True False 3. Match the following stack operations with their meaning. object pop(); boolean isEmpty(); push (object); integer size(); object top(); meanings are: - returns the number of elements stored -just removes the last inserted elements - returns the last inserted elements without removing...
Using Big O notation, indicate the time requirement of each of the following tasks in the...
Using Big O notation, indicate the time requirement of each of the following tasks in the worst case. Computing the sum of the first n even integers by using a for loop            [ Choose ] O(1) O(2n) O(n*log n ) O(2^n) O(log n) O(n^2) O(n) O(2) O(n^3)          Displaying all n integers in an array            [ Choose ] O(1) O(2n) O(n*log n ) O(2^n) O(log n) O(n^2) O(n) O(2) O(n^3)          Displaying all n integers in a sorted linked chain            [ Choose...
Write code in java Implement a method to build an AVL tree out of a sorted...
Write code in java Implement a method to build an AVL tree out of a sorted (ascending order) array of unique integers, with the fastest possible big O running time. You may implement private helper methods as necessary. If your code builds a tree that is other than an AVL tree, you will not get any credit. If your code builds an AVL tree, but is not the fastest big O implementation, you will get at most 12 points. You...
Java Please [(1)] A palindrome is a string that reads the same forwards as backwards. Using...
Java Please [(1)] A palindrome is a string that reads the same forwards as backwards. Using only a fixed number of stacks and queues, the stack and queue ADT functions, and a fixed number of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate [(2)] Let Q be a non-empty queue,...
There are N blocks, numbered from 0 to N-1, arranged in a row. A couple of...
There are N blocks, numbered from 0 to N-1, arranged in a row. A couple of frogs were sitting together on one block when they had a terrible quarrel. Now they want to jump away from one another so that the distance between them will be as large as possible. The distance between blocks numbered J and K, where JK, is computed as K-J+1. The frogs can only jump up, meaning that they can move from one block to another...
The following algorithm finds the initial substring of y that can be reversed and found in...
The following algorithm finds the initial substring of y that can be reversed and found in y. For example, longestInitialReverseSubstringLength(“aabaa”) = 5, because “aabaa” is the same string forwards and backwards, so the longest initial substring that can be reversed and found in the string is “aabaa”. Also, longestInitialReverseSubstringLength(“bbbbababbabbbbb”) is 6, because “babbbb” can be found in the string (see color-highlighted portions of the string), but no longer initial string exists reversed in any part of the string. longestInitialReverseSubstringLength(String y)...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT