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 :- 13

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 :- b

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 :- b

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 :- d

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 > i + j
• None of the other options is universally true. The expression depends on the values of first and last.

Answer :- b