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(n4 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 n4 log n.
- For every sufficiently large n, every input maze of dimension n can be solved within time proportional to n4 log n.
- For every sufficiently large n, there is an input maze of size n that requires time proportional to n4 log n.
- For some n, every input maze of size n requires time proportional to n4 log n.
Answer :- Click Here
3. You are executing an algorithm with worst-case time complexity O(n3) on a CPU that can perform 109 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(n2)
(C) f(n) is O(n4)
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”?
- 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 :- Click Here
