Nptel Design And Analysis Of Algorithms Week 1 Quiz Solutions

 

1.What does f(2000,3) return??

f(m,n) {

  ans = 1;

  count = 0;

  while (ans <= m) {

    count = count + 1;

    ans = ans * n;

  }

  return(count)

}

ANSWER :- 7

2.Suppose someone designs a new airline routing algorithm called MagicPath and claims that its worst-case complexity is O(n2 log n). Which of the following statements is inconsistent with this claim.

 For every n, for every input of size n, MagicPath is able to solve the problem in time proportional to n2.

 For some n, for every input of size n, MagicPath is able to solve the problem in time proportional to n2.

 For every sufficiently large n, there is an input of size n for which MagicPath requires time proportional to n2.

 For every sufficiently large n, there is an input of size n for which MagicPath requires time proportional to n3.

3.You are executing an algorithm with worst-case time complexity O(n4) on a CPU that can perform 108 operations per second. Which of the following is the most accurate guarantee for the time required to solve a worst case input of size 800?

 Under 5 minutes

 Under 5 hours

 Under 5 days

 Under 5 weeks

4.Suppose f(n) is n2 log n. Consider the following statements.

(A) f(n) is O(n √ n)

(B) f(n) is O(n2 √n)

(C) f(n) is O(n3)

Which of the following is true?

 (A), (B) and (C) are all not true.

 (B) and (C) are true but (A) is not true.

 (B) is true but (A) and (C) are not true.

 (A) and (B) are true but (C) is not true.

5.In the code fragment below, first and last are integer values and composite(x) is a function that returns true if x is not a prime number and false otherwise.

i = 0; j = 0; k = 0;

for (m = last; m >= first; m = m - 1){

  k = k + m;

  if (composite(m)){

    i = i + m;

  }else{

    j = j - m;

  }

}

if (…) {

  print("True");

}else{

  print("False");

}

Which of the following expressions can we put in place of the missing if condition (…) to ensure that the program prints "True"?

 k == i + j

 k == i - j

 k == j - i

 None of the other options is universally true. The expression depends on the values of first and last.

CONCLUSION : design and analysis of algorithm nptel assignment, assignment, design and analysis of algorithms week 1 quiz answers |, nargish gupta, design and analysis of algorithms, daa nptel week 1 quiz answers, design and analysis of algorithm nptel, daa assignement 1, cse, computer science, nptel, nptel 2023, week 1, assignment 1, daa solutions, nptel assignment solution 2023, Swayam nptel, Nptel assignment solutions, Swayam assingment solutions