2024 question paper

Design & Analysis of Algorithms

28 questions

1. Q1a. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following is TRUE? I. Quicksort runs in \Theta(n^2) time II. Bubblesort runs in \Theta(n^2) time III. Mergesort runs in \Theta(n) time IV. Insertion sort runs in \Theta(n) time - (i) I and II only - (ii) I and III only - (iii) II and IV only - (iv) I and IV only20242m

   Module 2: Divide and Conquer Paradigm and Heaps

   Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following is TRUE?

   I. Quicksort runs in $\Theta(n^2)$ time
   II. Bubblesort runs in $\Theta(n^2)$ time
   III. Mergesort runs in $\Theta(n)$ time
   IV. Insertion sort runs in $\Theta(n)$ time

   • (i) I and II only
   • (ii) I and III only
   • (iii) II and IV only
   • (iv) I and IV only

   View this question on its own page →

   CopySearch GoogleAsk AI
2. Q1b. Worst-case complexity of heap sort is - - (i) O(\log n) - (ii) O(n^2) - (iii) O(n \log n) - (iv) O(n)20242m

   Module 2: Divide and Conquer Paradigm and Heaps

   Worst-case complexity of heap sort is -

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

   View this question on its own page →

   CopySearch GoogleAsk AI
3. Q1c. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are: - (i) \Theta(n \log n), \Theta(n \log n) and \Theta(n^2) - (ii) \Theta(n^2), \Theta(n^2) and \Theta(n \log n) - (iii) \Theta(n^2), \Theta(n \log n) and \Theta(n \log n) - (iv) \Theta(n^2), \Theta(n \log n) and \Theta(n^2)20242m

   Module 2: Divide and Conquer Paradigm and Heaps

   The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

   • (i) $\Theta(n \log n)$, $\Theta(n \log n)$ and $\Theta(n^2)$
   • (ii) $\Theta(n^2)$, $\Theta(n^2)$ and $\Theta(n \log n)$
   • (iii) $\Theta(n^2)$, $\Theta(n \log n)$ and $\Theta(n \log n)$
   • (iv) $\Theta(n^2)$, $\Theta(n \log n)$ and $\Theta(n^2)$

   View this question on its own page →

   CopySearch GoogleAsk AI
4. Q1d. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is - (i) O(n) - (ii) O(\log n) - (iii) O(n \log n) - (iv) O(1)20242m

   Module 2: Divide and Conquer Paradigm and Heaps

   The minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers is

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

   View this question on its own page →

   CopySearch GoogleAsk AI
5. Q1e. What is the minimum number of stacks of size n required to implement a queue of size n - (i) one - (ii) two - (iii) three - (iv) four20242m

   Module 1: Introduction and Complexity Analysis

   What is the minimum number of stacks of size $n$ required to implement a queue of size $n$

   • (i) one
   • (ii) two
   • (iii) three
   • (iv) four

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1f. Dijkstra's algorithm is used to solve ______ problems? - (i) Single source shortest path - (ii) All pair shortest path - (iii) Sorting - (iv) Searching20242m

   Module 4: Graph and Tree Algorithms

   Dijkstra's algorithm is used to solve ______ problems?

   • (i) Single source shortest path
   • (ii) All pair shortest path
   • (iii) Sorting
   • (iv) Searching

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1g. The approach followed in Floyd Warshall's algorithm is - (i) Greedy approach - (ii) Dynamic approach - (iii) Backtracking - (iv) Divide and conquer20242m

   Module 4: Graph and Tree Algorithms

   The approach followed in Floyd Warshall's algorithm is

   • (i) Greedy approach
   • (ii) Dynamic approach
   • (iii) Backtracking
   • (iv) Divide and conquer

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q1h. Hamiltonian path problem is ______? - (i) NP Problem - (ii) NP Complete - (iii) P Class Problem - (iv) N Class Problem20242m

   Module 5: Tractable and Intractable Problems

   Hamiltonian path problem is ______?

   • (i) NP Problem
   • (ii) NP Complete
   • (iii) P Class Problem
   • (iv) N Class Problem

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q1i. Which of the following algorithms are used to find the shortest path from a source node to all other nodes in a weighted graph? - (i) BFS - (ii) Prim's Algorithm - (iii) Djikstra's Algorithm - (iv) Kruskal's Algorithm20242m

   Module 4: Graph and Tree Algorithms

   Which of the following algorithms are used to find the shortest path from a source node to all other nodes in a weighted graph?

   • (i) BFS
   • (ii) Prim's Algorithm
   • (iii) Djikstra's Algorithm
   • (iv) Kruskal's Algorithm

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q1j. Kruskal's Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a? - (i) DP Problem - (ii) Greedy Algorithm - (iii) Adhoc Problem - (iv) None of the above20242m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Kruskal's Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a?

    • (i) DP Problem
    • (ii) Greedy Algorithm
    • (iii) Adhoc Problem
    • (iv) None of the above

    View this question on its own page →

    CopySearch GoogleAsk AI
12. Q2a. Define Asymptotic Notation. Show that n^2 + 3\log n = O(n^2)20247m

    Module 1: Introduction and Complexity Analysis

    Define Asymptotic Notation. Show that $n^2 + 3\log n = O(n^2)$

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q2b. Solve the recurrence relation T(n) = 2T(n/2) + O(n)20247m

    Module 1: Introduction and Complexity Analysis

    Solve the recurrence relation $T(n) = 2T(n/2) + O(n)$

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q3a. Write Divide - And - Conquer Quick sort algorithm and analyze the algorithm for average time complexity.20247m

    Module 2: Divide and Conquer Paradigm and Heaps

    Write Divide - And - Conquer Quick sort algorithm and analyze the algorithm for average time complexity.

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q3b. Simulate Quick sort algorithm for the following example 25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 7820247m

    Module 2: Divide and Conquer Paradigm and Heaps

    Simulate Quick sort algorithm for the following example
    25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Construct the max heap for the following: 35 33 42 10 14 19 27 44 26 3120247m

    Module 2: Divide and Conquer Paradigm and Heaps

    Construct the max heap for the following: 35 33 42 10 14 19 27 44 26 31

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Explain Strassen's matrix multiplication and its time complexity.20247m

    Module 2: Divide and Conquer Paradigm and Heaps

    Explain Strassen's matrix multiplication and its time complexity.

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. State Huffman Tree. Explain with examples.20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    State Huffman Tree. Explain with examples.

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q5b. What are NP- hard and NP-complete problems?20247m

    Module 5: Tractable and Intractable Problems

    What are NP- hard and NP-complete problems?

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6a. How 8-Queen's problem can be solved using back tracking and explain with an example.20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    How 8-Queen's problem can be solved using back tracking and explain with an example.

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q6b. Distinguish greedy method and dynamic programming20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Distinguish greedy method and dynamic programming

    View this question on its own page →

    CopySearch GoogleAsk AI
23. Q7a. Construct minimum cost spanning tree using Kruskal's algorithm 20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Construct minimum cost spanning tree using Kruskal's algorithm
    

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q7b. Define spanning tree and minimum spanning tree20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Define spanning tree and minimum spanning tree

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8a. Apply single source shortest path algorithm for the following graph 20247m

    Module 4: Graph and Tree Algorithms

    Apply single source shortest path algorithm for the following graph

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8b. Explain Knapsack Problem.20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Explain Knapsack Problem.

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write short notes on: Cook's Theorem20247m

    Module 5: Tractable and Intractable Problems

    Write short notes on: Cook's Theorem

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write short notes on: Topological sorting20247m

    Module 4: Graph and Tree Algorithms

    Write short notes on: Topological sorting

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9c. Write short notes on: Travelling Salesman Problem20247m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write short notes on: Travelling Salesman Problem

    View this question on its own page →

    CopySearch GoogleAsk AI
30. Q9d. Write short notes on: Masters theorem20247m

    Module 1: Introduction and Complexity Analysis

    Write short notes on: Masters theorem

    View this question on its own page →

    CopySearch GoogleAsk AI