PyQdeck LogoPyQdeckSubjects

2022 question paper

Design and Analysis of Algorithms

25 questions

  1. Q1a. An adjacency matrix representation of a graph cannot contain information of (i) nodes (ii) edges (iii) direction of edges (iv) parallel edges20222m

    Module 3: Graph and Tree Algorithms

    An adjacency matrix representation of a graph cannot contain information of
    (i) nodes
    (ii) edges
    (iii) direction of edges
    (iv) parallel edges

    View this question on its own page →
    Search GoogleAsk AI
  2. Q1b. An algorithm is made up of two independent time complexities f(n) and g(n). Then the complexities of the algorithm is in the order of (i) f(n) \times g(n) (ii) \max \{ f(n), g(n) \} (iii) \min \{ f(n), g(n) \} (iv) f(n) + g(n)20222m

    Module 1: Introduction

    An algorithm is made up of two independent time complexities f(n)f(n) and g(n)g(n). Then the complexities of the algorithm is in the order of
    (i) f(n)×g(n)f(n) \times g(n)
    (ii) max⁡{f(n),g(n)}\max \{ f(n), g(n) \}
    (iii) min⁡{f(n),g(n)}\min \{ f(n), g(n) \}
    (iv) f(n)+g(n)f(n) + g(n)

    View this question on its own page →
    Search GoogleAsk AI
  3. Q1c. The minimum number of colors needed to color a graph having n > 3 vertices and 2 edges is (i) 2 (ii) 3 (iii) 4 (iv) 120222m

    Module 3: Graph and Tree Algorithms

    The minimum number of colors needed to color a graph having n>3n > 3 vertices and 2 edges is
    (i) 2
    (ii) 3
    (iii) 4
    (iv) 1

    View this question on its own page →
    Search GoogleAsk AI
  4. Q1d. BFS on a graph G = (V, E) has running time (i) O(|V| + |E|) (ii) O(|V|) (iii) O(|E|) (iv) None of these20222m

    Module 3: Graph and Tree Algorithms

    BFS on a graph G=(V,E)G = (V, E) has running time
    (i) O(∣V∣+∣E∣)O(|V| + |E|)
    (ii) O(∣V∣)O(|V|)
    (iii) O(∣E∣)O(|E|)
    (iv) None of these

    View this question on its own page →
    Search GoogleAsk AI
  5. Q1e. Which one is true of the following (i) all NP hard problems are NP complete (ii) all NP complete problems are NP hard (iii) some NP complete problems are NP hard (iv) None of these20222m

    Module 4: Tractable and Intractable Problems

    Which one is true of the following
    (i) all NP hard problems are NP complete
    (ii) all NP complete problems are NP hard
    (iii) some NP complete problems are NP hard
    (iv) None of these

    View this question on its own page →
    Search GoogleAsk AI
  6. Q1f. Which one of the following functions is asymptotically smallest? (i) 2^n (ii) n^{\log n} (iii) n^{\sqrt{n}} (iv) (100)^{(\log n)^{1/3}} + (\log \log n)^{2/3}20222m

    Module 1: Introduction

    Which one of the following functions is asymptotically smallest?
    (i) 2n2^n
    (ii) nlog⁡nn^{\log n}
    (iii) nnn^{\sqrt{n}}
    (iv) (100)(log⁡n)1/3+(log⁡log⁡n)2/3(100)^{(\log n)^{1/3}} + (\log \log n)^{2/3}

    View this question on its own page →
    Search GoogleAsk AI
  7. Q1g. Which of the following algorithm solves the All Pair Shortest Path problem (i) Dijkstra's (ii) Floyd's Warshall's (iii) Prim's (iv) Kruskal's20222m

    Module 3: Graph and Tree Algorithms

    Which of the following algorithm solves the All Pair Shortest Path problem
    (i) Dijkstra's
    (ii) Floyd's Warshall's
    (iii) Prim's
    (iv) Kruskal's

    View this question on its own page →
    Search GoogleAsk AI
  8. Q1h. The average number of comparisons performed by merge sort algorithm in merging two sorted lists of 2 elements is (i) 8/5 (ii) 11/7 (iii) 11/6 (iv) 8/320222m

    Module 1: Introduction

    The average number of comparisons performed by merge sort algorithm in merging two sorted lists of 2 elements is
    (i) 8/5
    (ii) 11/7
    (iii) 11/6
    (iv) 8/3

    View this question on its own page →
    Search GoogleAsk AI
  9. Q1i. Which one of the following statement is correct? (i) If A \le_p B and B \in P then A \in P (ii) If A \le_p B and $A otin P then B otin P$ (iii) If A \le_p B and B \le_p C then A \le_p C (iv) All of these20222m

    Module 4: Tractable and Intractable Problems

    Which one of the following statement is correct?
    (i) If A≤pBA \le_p B and B∈PB \in P then A∈PA \in P
    (ii) If A≤pBA \le_p B and $A
    otin Pthen then B
    otin P$
    (iii) If A≤pBA \le_p B and B≤pCB \le_p C then A≤pCA \le_p C
    (iv) All of these

    View this question on its own page →
    Search GoogleAsk AI
  10. Q1j. Kruskal algorithm is a (i) Divide & conquer algorithm (ii) Branch and bound algorithm (iii) Greedy algorithm (iv) Dynamic programming20222m

    Module 2: Fundamental Algorithmic Strategies

    Kruskal algorithm is a
    (i) Divide & conquer algorithm
    (ii) Branch and bound algorithm
    (iii) Greedy algorithm
    (iv) Dynamic programming

    View this question on its own page →
    Search GoogleAsk AI
  12. Q2a. Solve the following recurrence by successive substitution method: f(1) = 1 \quad \text{if } n=1 f(n) = 3f(n/2) + 6 \quad \text{if } n > 120227m

    Module 1: Introduction

    Solve the following recurrence by successive substitution method:
    f(1)=1if n=1f(1) = 1 \quad \text{if } n=1
    f(n)=3f(n/2)+6if n>1f(n) = 3f(n/2) + 6 \quad \text{if } n > 1

    View this question on its own page →
    Search GoogleAsk AI
  13. Q2b. Write the Knuth-Morris-Pratt algorithm for pattern matching. Apply the KMP algorithm for the pattern p = "ababaca" and string s = "bacbabababacaab". Show every step.20227m

    Module 2: Fundamental Algorithmic Strategies

    Write the Knuth-Morris-Pratt algorithm for pattern matching. Apply the KMP algorithm for the pattern p="ababaca"p = "ababaca" and string s="bacbabababacaab"s = "bacbabababacaab". Show every step.

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3a. Give step by step procedure to find minimal spanning tree for the given graph. ![image](https://9lrt4yspyx.ufs.sh/f/z1z03jdN1p04sU7KeS0RokTQjiuapSXvByEJLFr8weIGhWCq)20227m

    Module 3: Graph and Tree Algorithms

    Give step by step procedure to find minimal spanning tree for the given graph.

    image

    View this question on its own page →
    Search GoogleAsk AI
  15. Q3b. Write the algorithm for quick sort. Find the best-case, worst-case and average-case time complexities of this algorithm.20227m

    Module 2: Fundamental Algorithmic Strategies

    Write the algorithm for quick sort. Find the best-case, worst-case and average-case time complexities of this algorithm.

    View this question on its own page →
    Search GoogleAsk AI
  16. Q4a. Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm. ![image](https://9lrt4yspyx.ufs.sh/f/z1z03jdN1p04cA0M12VDrIj0ikyQ82dzRXKGqChPbOmcuBt6)20227m

    Module 3: Graph and Tree Algorithms

    Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm.

    image

    View this question on its own page →
    Search GoogleAsk AI
  17. Q4b. State the graph coloring problem and write the algorithm. Apply backtracking technique to solve the 3-colouring problem for the following graph. ![image](https://9lrt4yspyx.ufs.sh/f/z1z03jdN1p04sDZHdx0RokTQjiuapSXvByEJLFr8weIGhWCq)20227m

    Module 2: Fundamental Algorithmic Strategies

    State the graph coloring problem and write the algorithm. Apply backtracking technique to solve the 3-colouring problem for the following graph.

    image

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5a. Differentiate between divide & conquer, greedy method and dynamic programming with suitable examples.20227m

    Module 2: Fundamental Algorithmic Strategies

    Differentiate between divide & conquer, greedy method and dynamic programming with suitable examples.

    View this question on its own page →
    Search GoogleAsk AI
  19. Q5b. Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming. Also discuss the complexity involved. A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100)20227m

    Module 2: Fundamental Algorithmic Strategies

    Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming. Also discuss the complexity involved.
    A(10×20)∗B(20×50)∗C(50×1)∗D(1×100)A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100)

    View this question on its own page →
    Search GoogleAsk AI
  20. Q6a. Explain solution pseudocode for N-Queens problem using backtracking.20227m

    Module 2: Fundamental Algorithmic Strategies

    Explain solution pseudocode for N-Queens problem using backtracking.

    View this question on its own page →
    Search GoogleAsk AI
  21. Q6b. Find Huffman codes for the text of characters with given frequencies: | Characters | T | I | V | K | L | E | O | Z | P | R | |---|---|---|---|---|---|---|---|---|---|---| | Frequencies | 43 | 38 | 16 | 8 | 50 | 12 | 56 | 13 | 22 | 7 |20227m

    Module 2: Fundamental Algorithmic Strategies

    Find Huffman codes for the text of characters with given frequencies:

    Characters T I V K L E O Z P R
    Frequencies 43 38 16 8 50 12 56 13 22 7
    View this question on its own page →
    Search GoogleAsk AI
  23. Q7a. What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.20227m

    Module 3: Graph and Tree Algorithms

    What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.

    View this question on its own page →
    Search GoogleAsk AI
  24. Q7b. Define P-Class, NP-class, NP-complete class and NP-hard class of problems. What is the relation between them?20227m

    Module 4: Tractable and Intractable Problems

    Define P-Class, NP-class, NP-complete class and NP-hard class of problems. What is the relation between them?

    View this question on its own page →
    Search GoogleAsk AI
  25. Q8a. Find the optimal solution using greedy criteria for a knapsack having capacity 100 kg for the following list of items having values and weights as shown in the table. | Item | Value | Weight | |---|---|---| | I_1 | 10 | 15 | | I_2 | 20 | 25 | | I_3 | 30 | 35 | | I_4 | 40 | 45 | | I_5 | 50 | 55 |20227m

    Module 2: Fundamental Algorithmic Strategies

    Find the optimal solution using greedy criteria for a knapsack having capacity 100 kg for the following list of items having values and weights as shown in the table.

    Item Value Weight
    I1I_1 10 15
    I2I_2 20 25
    I3I_3 30 35
    I4I_4 40 45
    I5I_5 50 55
    View this question on its own page →
    Search GoogleAsk AI
  26. Q8b. State master's theorem and find the time complexity for the following recurrence: T(n) = 2T(n^{1/2}) + \log n20227m

    Module 1: Introduction

    State master's theorem and find the time complexity for the following recurrence:
    T(n)=2T(n1/2)+log⁡nT(n) = 2T(n^{1/2}) + \log n

    View this question on its own page →
    Search GoogleAsk AI
  27. Q9. Write short notes on any two of the following: (i) Asymptotic Notations (ii) Clique decision problem (iii) Max-flow-min-cut theorem (iv) Union-Find Algorithm202214m

    Module 1: Introduction

    Write short notes on any two of the following:
    (i) Asymptotic Notations
    (ii) Clique decision problem
    (iii) Max-flow-min-cut theorem
    (iv) Union-Find Algorithm

    View this question on its own page →
    Search GoogleAsk AI
Next year2023