2022 question paper

Design & Analysis of Algorithms

21 questions

1. Q1a. Any decision trees that sorts n elements has height: - (i) \Omega(\lg n) - (ii) \Omega(n) - (iii) \Omega(n \lg n) - (iv) \Omega(n^2)20222m

   Module 1: Introduction and Complexity Analysis

   Any decision trees 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
2. Q1b. Which 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 above20222m

   Module 1: Introduction and Complexity Analysis

   Which 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
3. Q1c. The complexity algorithm of binary search is: - (i) O(n) - (ii) O(\log n) - (iii) O(n^2) - (iv) O(n \log n)20222m

   Module 2: Divide and Conquer Paradigm and Heaps

   The complexity algorithm of binary search 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
4. Q1d. In linear search algorithm the worst case occurs when: - (i) the item is somewhere in the middle of the array - (ii) the item is not in the array at all - (iii) the item is the last element in the array - (iv) the item is the last element in the array or is not there at all20222m

   Module 1: Introduction and Complexity Analysis

   In linear search algorithm the worst case occurs when:

   • (i) the item is somewhere in the middle of the array
   • (ii) the item is not in the array at all
   • (iii) the item is the last element in the array
   • (iv) the item is the last element in the array or is not there at all

   View this question on its own page →

   CopySearch GoogleAsk AI
5. Q1e. Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity? - (i) Insertion sort with time complexity O(kn) - (ii) Heap sort with time complexity O(n \log k) - (iii) Quick sort with time complexity O(k \log k) - (iv) Merge sort with time complexity O(k \log k)20222m

   Module 1: Introduction and Complexity Analysis

   Given an unsorted array. The array has this property that every element in array is at most $k$ distance from its position in sorted array where $k$ is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

   • (i) Insertion sort with time complexity $O(kn)$
   • (ii) Heap sort with time complexity $O(n \log k)$
   • (iii) Quick sort with time complexity $O(k \log k)$
   • (iv) Merge sort with time complexity $O(k \log k)$

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1f. Approach of dynamic programming is similar to: - (i) parsing - (ii) hash table - (iii) divide and conquer algorithm - (iv) greedy algorithm20222m

   Module 3: Greedy, Dynamic Programming and Other Paradigms

   Approach of dynamic programming is similar to:

   • (i) parsing
   • (ii) hash table
   • (iii) divide and conquer algorithm
   • (iv) greedy algorithm

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1g. In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of: - (i) divide/break - (ii) sorting/divide - (iii) conquer/solve - (iv) merge/combine20222m

   Module 2: Divide and Conquer Paradigm and Heaps

   In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of:

   • (i) divide/break
   • (ii) sorting/divide
   • (iii) conquer/solve
   • (iv) merge/combine

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q1h. A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements '1' and '7' are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is: - (i) 10, 8, 7, 5, 3, 2, 1 - (ii) 10, 8, 7, 2, 3, 1, 5 - (iii) 10, 8, 7, 1, 2, 3, 5 - (iv) 10, 8, 7, 3, 2, 1, 520222m

   Module 2: Divide and Conquer Paradigm and Heaps

   A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements '1' and '7' are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is:

   • (i) 10, 8, 7, 5, 3, 2, 1
   • (ii) 10, 8, 7, 2, 3, 1, 5
   • (iii) 10, 8, 7, 1, 2, 3, 5
   • (iv) 10, 8, 7, 3, 2, 1, 5

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q1i. If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called: - (i) dynamic programming - (ii) greedy - (iii) divide and conquer - (iv) recursion20222m

   Module 2: Divide and Conquer Paradigm and Heaps

   If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called:

   • (i) dynamic programming
   • (ii) greedy
   • (iii) divide and conquer
   • (iv) recursion

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q1j. The choice of polynomial class has led to the development of an extensive theory called: - (i) computational complexity - (ii) time complexity - (iii) problem complexity - (iv) decision complexity20222m

    Module 5: Tractable and Intractable Problems

    The choice of polynomial class has led to the development of an extensive theory called:

    • (i) computational complexity
    • (ii) time complexity
    • (iii) problem complexity
    • (iv) decision complexity

    View this question on its own page →

    CopySearch GoogleAsk AI
12. Q2a. Calculate the time complexity of the following problem using divide and conquer strategies: (i) T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n, \quad n > 2 (ii) T(n) = T(n-1) + 1/n, \quad n > 120227m

    Module 1: Introduction and Complexity Analysis

    Calculate the time complexity of the following problem using divide and conquer strategies:
    (i) $$T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n, \quad n > 2$$
    (ii) $$T(n) = T(n-1) + 1/n, \quad n > 1$$

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q2b. Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method: ``c rec(n) { if (n <= 1) return(1); else { rec(n / 2); for (i = 1; i <= n; i++) printf("algorithm"); } } ``20227m

    Module 1: Introduction and Complexity Analysis

    Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method:

    rec(n) {
        if (n <= 1) return(1);
        else {
            rec(n / 2);
            for (i = 1; i <= n; i++)
                printf("algorithm");
        }
    }
    

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q3a. Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.20227m

    Module 2: Divide and Conquer Paradigm and Heaps

    Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q3b. What are the rules of manipulate Big-Oh expression and about the typical growth rates of algorithms.20227m

    Module 1: Introduction and Complexity Analysis

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

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. What is heap sort? What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?20227m

    Module 2: Divide and Conquer Paradigm and Heaps

    What is heap sort? What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Explain how radix sort works, to what inputs it can be applied and what is its asymptotic complexity?20227m

    Module 1: Introduction and Complexity Analysis

    Explain how radix sort works, to what inputs it can be applied and what is its asymptotic complexity?

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5. 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. 202214m

    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
19. Q6. Find the optimal way to multiply the following matrices to perform the fewest multiplications: | Matrix | Dimension | | :--- | :--- | | A_1 | 5 \times 11 | | A_2 | 11 \times 4 | | A_3 | 4 \times 15 | | A_4 | 15 \times 23 |202214m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Find the optimal way to multiply the following matrices to perform the fewest multiplications:

    Matrix	Dimension
    $A_1$	$5 \times 11$
    $A_2$	$11 \times 4$
    $A_3$	$4 \times 15$
    $A_4$	$15 \times 23$

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q7. You are given a graph containing n vertices and m edges and given that the graph doesn't contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?202214m

    Module 4: Graph and Tree Algorithms

    You are given a graph containing $n$ vertices and $m$ edges and given that the graph doesn't contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q8. What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, prove that it yields an optimal solution.202214m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, prove that it yields an optimal solution.

    View this question on its own page →

    CopySearch GoogleAsk AI
23. Q9b. Write short notes on: Approximation algorithms20227m

    Module 5: Tractable and Intractable Problems

    Write short notes on: Approximation algorithms

    View this question on its own page →

    CopySearch GoogleAsk AI