Hello learners In this article we are going to discuss NPTEL Design and analysis of algorithms Assignment 1 Answers. All the Answers provided below to help the students as a reference, You must submit your assignment with your own knowledge and use this article as reference only.
About the course:-
This course will cover basic concepts in the design and analysis of algorithms.
- Asymptotic complexity, O() notation
- Sorting and search
- Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees
- Design techniques: divide and conquer, greedy, dynamic programming
- Data structures: heaps, union of disjoint sets, search trees
- Intractability
NPTEL Design and analysis of algorithms Assignment 1 Answers 2024:
1. An image processing application begins with two n×n matrices A and B. The first phase of preprocessing the inputs takes O(n2) steps for each of A and B. The second step involves a convolution of A and B to yield a new matrix C in time O(n3). This is followed by an edge detection phase that takes times O(n2) for matrix C. What is the most accurate and concise description of the complexity of the overall algorithm?
Answer :- b
2. We are trying to determine the worst case time complexity of a library function that is provided to us, whose code we cannot read. We test the function by feeding large numbers of random inputs of different sizes. We find that for inputs of size 400 and 4,000, the function always returns well within one second, but for inputs of size 40,000 it sometimes takes a couple of seconds and for inputs of size 400,000 it sometimes takes a few minutes. What is a reasonable conclusion we can draw about the worst case time complexity of the library function? (You can assume, as usual, that a typical desktop PC performs 109 basic operations per second.)
Answer :- b
3. Suppose f(n) is 252n3+164n2+507 and g(n) is n4 + 5n + 12. Let h(n) be a third, unknown function. Which of the following is not possible.
Answer :- b
4. How many times is the comparison i >= n performed in the following program?
int i = 300, n = 150;
main(){
while (i >= n){
i = i-2;
n = n+1;
}
}Answer :- c
5. If T(n) is O(n2 √ n) which of the following is false?
Answer :- a
