2019 question paper

Design & Analysis of Algorithms

23 questions

1. Q1a. In the following C++ function, let n >= m. ``cpp int gcd(int n, int m) { if (n % m == 0) return m; if (n < m) swap(n, m); while (m > 0) { n = n % m; swap(n, m); } return n; } `` What is the time complexity of the above function assuming n > m? - (i) \Theta(\log n) - (ii) \Omega(n) - (iii) \Theta(\log \log n) - (iv) \Theta(\sqrt{n})20192m

   Module 1: Introduction and Complexity Analysis

   In the following C++ function, let $n >= m$.

   int gcd(int n, int m) {
     if (n % m == 0) return m;
     if (n < m) swap(n, m);
     while (m > 0) {
       n = n % m;
       swap(n, m);
     }
     return n;
   }
   

   What is the time complexity of the above function assuming $n > m$?

   • (i) $\Theta(\log n)$
   • (ii) $\Omega(n)$
   • (iii) $\Theta(\log \log n)$
   • (iv) $\Theta(\sqrt{n})$

   View this question on its own page →

   CopySearch GoogleAsk AI
2. Q1b. Time complexity of Kadane's Algorithm is: - (i) O(n) - (ii) O(n^2) - (iii) O(n \log n) - (iv) O(n(\log n)^2)20192m

   Module 3: Greedy, Dynamic Programming and Other Paradigms

   Time complexity of Kadane's Algorithm is:

   • (i) $O(n)$
   • (ii) $O(n^2)$
   • (iii) $O(n \log n)$
   • (iv) $O(n(\log n)^2)$

   View this question on its own page →

   CopySearch GoogleAsk AI
3. Q1c. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three? - (i) 1/8 - (ii) 1 - (iii) 8 - (iv) 820192m

   Module 4: Graph and Tree Algorithms

   Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $1/2$. What is the expected number of unordered cycles of length three?

   • (i) 1/8
   • (ii) 1
   • (iii) 8
   • (iv) 8

   View this question on its own page →

   CopySearch GoogleAsk AI
4. Q1d. Any decision tree that sorts n elements has height: - (i) \Omega(\lg n) - (ii) \Omega(n) - (iii) \Omega(n \lg n) - (iv) \Omega(n^2)20192m

   Module 1: Introduction and Complexity Analysis

   Any decision tree that sorts $n$ elements has height:

   • (i) $\Omega(\lg n)$
   • (ii) $\Omega(n)$
   • (iii) $\Omega(n \lg n)$
   • (iv) $\Omega(n^2)$

   View this question on its own page →

   CopySearch GoogleAsk AI
5. Q1e. An all-pairs shortest-paths problem is efficiently solved using: - (i) Dijkstra's algorithm - (ii) Bellman-Ford algorithm - (iii) Kruskal algorithm - (iv) Floyd-Warshall algorithm20192m

   Module 3: Greedy, Dynamic Programming and Other Paradigms

   An all-pairs shortest-paths problem is efficiently solved using:

   • (i) Dijkstra's algorithm
   • (ii) Bellman-Ford algorithm
   • (iii) Kruskal algorithm
   • (iv) Floyd-Warshall algorithm

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1f. Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? - (i) In adjacency list representation, space is saved for sparse graphs. - (ii) DFS and BFS can be done in O(V+E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. - (iii) Adding a vertex in adjacency list representation is easier than adjacency matrix representation. - (iv) All of the above20192m

   Module 4: Graph and Tree Algorithms

   Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

   • (i) In adjacency list representation, space is saved for sparse graphs.
   • (ii) DFS and BFS can be done in $O(V+E)$ time for adjacency list representation. These operations take $O(V^2)$ time in adjacency matrix representation.
   • (iii) Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
   • (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1g. Which of the following is true about Huffman Coding? - (i) Huffman coding may become lossy in some cases. - (ii) Huffman codes may not be optimal lossless codes in some cases. - (iii) In Huffman coding, no code is prefix of any other code. - (iv) All of the above20192m

   Module 3: Greedy, Dynamic Programming and Other Paradigms

   Which of the following is true about Huffman Coding?

   • (i) Huffman coding may become lossy in some cases.
   • (ii) Huffman codes may not be optimal lossless codes in some cases.
   • (iii) In Huffman coding, no code is prefix of any other code.
   • (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q1h. Which one of the following is an application of Queue Data Structure? - (i) When a resource is shared among multiple consumers - (ii) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes - (iii) Load balancing - (iv) All of the above20192m

   Module 1: Introduction and Complexity Analysis

   Which one of the following is an application of Queue Data Structure?

   • (i) When a resource is shared among multiple consumers
   • (ii) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
   • (iii) Load balancing
   • (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q1j. The complexity of binary search algorithm is: - (i) O(n) - (ii) O(\log n) - (iii) O(n^2) - (iv) O(n \log n)20192m

   Module 2: Divide and Conquer Paradigm and Heaps

   The complexity of binary search algorithm is:

   • (i) $O(n)$
   • (ii) $O(\log n)$
   • (iii) $O(n^2)$
   • (iv) $O(n \log n)$

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q2a. Discuss the steps in mathematical analysis for recursive algorithm. Do the same for finding the factorial of a number?20197m

    Module 1: Introduction and Complexity Analysis

    Discuss the steps in mathematical analysis for recursive algorithm. Do the same for finding the factorial of a number?

    View this question on its own page →

    CopySearch GoogleAsk AI
12. Q2b. What are the rules of manipulate Big-Oh expression? Write about the typical growth rates of algorithms.20197m

    Module 1: Introduction and Complexity Analysis

    What are the rules of manipulate Big-Oh expression? Write about the typical growth rates of algorithms.

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q3a. What are the advantages of merge-sort over the quick-sort algorithm?20197m

    Module 2: Divide and Conquer Paradigm and Heaps

    What are the advantages of merge-sort over the quick-sort algorithm?

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q3b. What is the time complexity of the matrix multiplication and Strassen's algorithm?20197m

    Module 2: Divide and Conquer Paradigm and Heaps

    What is the time complexity of the matrix multiplication and Strassen's algorithm?

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q4. Prove that if f_1(n) = O(g_1(n)) and f_2(n) = O(g_2(n)), then f_1(n) + f_2(n) = O(g_1(n) + g_2(n)).201914m

    Module 1: Introduction and Complexity Analysis

    Prove that if $f_1(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) + f_2(n) = O(g_1(n) + g_2(n))$.

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q5a. What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.20197m

    Module 5: Tractable and Intractable Problems

    What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q5b. Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.20197m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q6. Consider the array A = \{26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 21, 28, 38, 7, 12, 14, 20, 35, 39, 3\}. Create binary search tree with one more attribute its size of node. Retrieve 17th smallest element in the tree and rank the 12th element.201914m

    Module 4: Graph and Tree Algorithms

    Consider the array $A = \{26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 21, 28, 38, 7, 12, 14, 20, 35, 39, 3\}$. Create binary search tree with one more attribute its size of node. Retrieve 17th smallest element in the tree and rank the 12th element.

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q7. What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the graph G = (V, E) given below. Find the minimum spanning tree by Prim's algorithms. 201914m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the graph $G = (V, E)$ given below. Find the minimum spanning tree by Prim's algorithms.

    

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q8. Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the following graph using state space tree. Assume three colours red, green and blue. 201914m

    Module 5: Tractable and Intractable Problems

    Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the following graph using state space tree. Assume three colours red, green and blue.

    

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q9a. Write short notes on: Kruskal algorithms.20197m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write short notes on: Kruskal algorithms.

    View this question on its own page →

    CopySearch GoogleAsk AI
23. Q9b. Write short notes on: Branch and bound technique20197m

    Module 5: Tractable and Intractable Problems

    Write short notes on: Branch and bound technique

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q9c. Write short notes on: Amortized analysis.20197m

    Module 1: Introduction and Complexity Analysis

    Write short notes on: Amortized analysis.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q9d. Write short notes on: Divide-N-Conquer vs Dynamic Programming20197m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write short notes on: Divide-N-Conquer vs Dynamic Programming

    View this question on its own page →

    CopySearch GoogleAsk AI