Q1:Consider thefollowing code: for (j=1;j<n;j++) for (k=1;k<15;k++) for(l=5; l<n

Question

Q1:Consider thefollowing code:

for (j=1;j<n;j++)

for (k=1;k<15;k++)

for(l=5; l<n;l++)

{

Do_something_constant();

}

What order is theexecution of this code?

1O(n)

2O(n3)

3O(n2 log n)

4O(n2)

Q No. 2Given a list of N integers, the 3-sumproblem is to determine whether there exists 3 integers

in the list (notnecessarily distinct) such that x + y + z = 0. Suppose that you areexecuting the

brute force algorithmbelow on a computer that executes 1 billion operations(addition,

increment, orcomparison) per second.

int brute(int a[], intN)

{

int i, j, k;

for (i = 0; i < N;i++)

for (j = 0; j < N;j++)

for (k = 0; k < N;k++)

if (a[i] + a[j] + a[k]== 0) return 1;

return 0; // nonefound

}

(a) Estimate how manyseconds it will take (in the worst case) to solve a problem of sizeN =

(b) Of size N = 10,000?

What is the solution to the recurrenceT(n) =T(n/2)+n,T(1) = 1

1 O(logn)

2 O(n)

3 O(nlogn)

4 O(n2)

T(1) = 5

Q:5 Consider the following problem:You are given a sequence of n integers that contains log2 ndifferent integers.For example, n = 8, log(8) = 2:{3,5,3,5,3,5,5,5}; the list of 8 numbers is made up of only twodistinct integers 3 and 5. Design an algorithm to sort thissequence using O(nloglogn) element comparisons (which is better thanO(nlogn)). Prove that youralgorithm is indeed O(nloglogn) [Hint: use variation ofheap sort.]

Explanation / Answer

ITS HELPFUL TO YOU.....

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.