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.

- What is the best-case running time of Algorithm X?
- 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.

- Give the algorithm pseudocode.
- Implement your algorithm and test it using java.
- 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.

- Give the algorithm pseudocode.
- Implement your algorithm and test it using java.
- 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

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 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
(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 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 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 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 5 minutes ago

asked 11 minutes ago

asked 26 minutes ago

asked 26 minutes ago

asked 27 minutes ago

asked 33 minutes ago

asked 35 minutes ago

asked 35 minutes ago

asked 48 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago