NPTEL Design and Analysis of Algorithms Week 1 Assignment Answers 2024

1. How many times is the while condition tested if the following function is called as f(165,15)?

f(m,n) {
  ans = 1;
  while (m >= 0) {
    ans = ans * (ans + 1);
    m = m-n;
  }
  return(ans)
}

Answer :- Click Here

2. A new game in the appstore called AmazeMe involves finding a path out of an n-dimensional maze. The authors of the game claim there is a solution with worst case complexity O(n⁴ log n). where n is the number of dimensions.

From this, we can conclude that:

For every sufficiently large n, every input maze of dimension n requires time proportional to n⁴ log n.
For every sufficiently large n, every input maze of dimension n can be solved within time proportional to n⁴ log n.
For every sufficiently large n, there is an input maze of size n that requires time proportional to n⁴ log n.
For some n, every input maze of size n requires time proportional to n⁴ log n.

Answer :- Click Here

3. You are executing an algorithm with worst-case time complexity O(n³) on a CPU that can perform 10⁹ operations per second. What is the most accurate bound for the time required to solve a worst case input of size 30,000?

Under 8 minutes
Under 8 hours
Under 8 days
Under 8 months

Answer :-

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

(A) f(n) is O(n log n)
(B) f(n) is O(n²)
(C) f(n) is O(n⁴)

Which of the following is true?

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

Answer :- Click Here

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