2023 question paper

Design & Analysis of Algorithms

28 questions

1. Q1a. The fractional Knapsack problem can be solved by using: - (i) Greedy method - (ii) Divide and conquer method - (iii) Dynamic programming - (iv) None of these20232m

   Module 3: Greedy, Dynamic Programming and Other Paradigms

   The fractional Knapsack problem can be solved by using:

   • (i) Greedy method
   • (ii) Divide and conquer method
   • (iii) Dynamic programming
   • (iv) None of these

   View this question on its own page →

   CopySearch GoogleAsk AI
2. Q1b. BFS on a graph G=(V,E) has running time: - (i) O(|V|+|E|) - (ii) O(|V|) - (iii) O(|E|) - (iv) None of the above20232m

   Module 4: Graph and Tree Algorithms

   BFS on a graph $G=(V,E)$ has running time:

   • (i) $O(|V|+|E|)$
   • (ii) $O(|V|)$
   • (iii) $O(|E|)$
   • (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) $O(|V|+|E|)$

   Explanation

   Breadth-First Search (BFS) using adjacency list:

   Complexity Analysis

   1. Initialization: $O(|V|)$ — mark all vertices unvisited, enqueue source.
   2. Each vertex is enqueued and dequeued exactly once → $O(|V|)$.
   3. Each edge is examined twice (once from each endpoint in undirected graph, once in directed) when exploring adjacency list of its source vertex → $O(|E|)$.

   Total:
   $$T(V,E) = O(|V|) + O(|E|) = O(|V|+|E|)$$

   Why other options are wrong

   • (ii) $O(|V|)$: Ignores edge scanning. Correct only if graph is empty ($|E|=0$).
   • (iii) $O(|E|)$: Ignores vertex initialization and isolated vertices.
   • Adjacency matrix BFS would be $O(|V|^2)$, but with adjacency list (standard) it is $O(|V|+|E|)$.

   Final Answer

   BFS running time is $O(|V|+|E|)$ → Option (i).

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) 120232m

   Module 4: Graph and Tree Algorithms

   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) 1

   View this question on its own page →

   CopySearch GoogleAsk AI
4. Q1g. Level order traversal of a rooted tree can be done by starting from root and performing: - (i) Depth first search - (ii) Breadth first search - (iii) Pre-order traversal - (iv) In-order traversal20232m

   Module 4: Graph and Tree Algorithms

   Level order traversal of a rooted tree can be done by starting from root and performing:

   • (i) Depth first search
   • (ii) Breadth first search
   • (iii) Pre-order traversal
   • (iv) In-order traversal

   View this question on its own page →

   CopySearch GoogleAsk AI
5. Q1h. An algorithm is made up of two independent time complexities f(n) and g(n). Then the complexity of the algorithm is in 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)20232m

   Module 1: Introduction and Complexity Analysis

   An algorithm is made up of two independent time complexities $f(n)$ and $g(n)$. Then the complexity of the algorithm is in 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)$

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1i. Which of the following standard algorithms is not a greedy algorithm? - (i) Dijkstra's shortest path algorithm - (ii) Kruskal algorithm - (iii) Bellman ford shortest path algorithm - (iv) Prim's algorithm20232m

   Module 3: Greedy, Dynamic Programming and Other Paradigms

   Which of the following standard algorithms is not a greedy algorithm?

   • (i) Dijkstra's shortest path algorithm
   • (ii) Kruskal algorithm
   • (iii) Bellman ford shortest path algorithm
   • (iv) Prim's algorithm

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1j. The node removal of which makes a graph disconnected is called: - (i) Pendant vertex - (ii) Bridge - (iii) Articulation point - (iv) Coloured vertex20232m

   Module 4: Graph and Tree Algorithms

   The node removal of which makes a graph disconnected is called:

   • (i) Pendant vertex
   • (ii) Bridge
   • (iii) Articulation point
   • (iv) Coloured vertex

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q2a. Discuss the average, worst, and best time complexity of the algorithm. Give suitable examples.20237m

   Module 1: Introduction and Complexity Analysis

   Discuss the average, worst, and best time complexity of the algorithm. Give suitable examples.

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q2b. Write the algorithm for quick-sort and find its complexity.20237m

   Module 2: Divide and Conquer Paradigm and Heaps

   Write the algorithm for quick-sort and find its complexity.

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q3a. Construct the Huffman coding tree for the text of characters with given frequencies. | Character | T | I | V | K | L | E | O | Z | P | R | |----------:|:--:|:--:|:--:|:-:|:--:|:--:|:--:|:--:|:--:|:--:| | Frequency | 43 | 38 | 16 | 8 | 56 | 12 | 41 | 13 | 22 | 6 |20237m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Construct the Huffman coding tree for the text of characters with given frequencies.

    Character	T	I	V	K	L	E	O	Z	P	R
    Frequency	43	38	16	8	56	12	41	13	22	6

    View this question on its own page →

    CopySearch GoogleAsk AI
11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q3b. State the general Knapsack problem. Write a greedy algorithm for this problem and derive its time complexity.20237m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    State the general Knapsack problem. Write a greedy algorithm for this problem and derive its time complexity.

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q4a. State Master's theorem and find the time complexity for the following recurrence: T(n) = 2T(n^{1/2}) + \log n20237m

    Module 1: Introduction and Complexity Analysis

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

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q4b. What is negative weight-cycle? Write Bellman-Ford algorithm to find single shortest distance of a directed graph.20237m

    Module 4: Graph and Tree Algorithms

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

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q5a. Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming: A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100)20237m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming: $$A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100)$$

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q5b. Write Knuth-Morris-Pratt (KMP) algorithm for string matching problem.20237m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write Knuth-Morris-Pratt (KMP) algorithm for string matching problem.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q6a. Write an algorithm to find a minimum spanning tree (MST) for an undirected graph. Estimate the time complexity of your algorithm.20238m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write an algorithm to find a minimum spanning tree (MST) for an undirected graph. Estimate the time complexity of your algorithm.

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q6b. Using greedy strategy, schedule the following jobs within deadline so as to maximize the profit. | Job i | 1 | 2 | 3 | 4 | | :--- | :--- | :--- | :--- | :--- | | Deadline d | 3 | 2 | 3 | 1 | | Profit g | 9 | 7 | 7 | 2 |20236m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Using greedy strategy, schedule the following jobs within deadline so as to maximize the profit.

    Job $i$	1	2	3	4
    Deadline $d$	3	2	3	1
    Profit $g$	9	7	7	2

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q7a. Write an algorithm for n-queen's problem, find its time complexity and explain the algorithm using an example.20237m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write an algorithm for $n$-queen's problem, find its time complexity and explain the algorithm using an example.

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q7b. Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm. (Graph image reference in source document)20237m

    Module 4: 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. (Graph image reference in source document)

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q8a. Define the classes P and NP.20232m

    Module 5: Tractable and Intractable Problems

    Define the classes $P$ and $NP$.

    View this question on its own page →

    CopySearch GoogleAsk AI
22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q8b. Discuss what you mean by polynomial reduction.20232m

    Module 5: Tractable and Intractable Problems

    Discuss what you mean by polynomial reduction.

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q8c. Discuss diagrammatically the relation among P class, NP class, NP hard and NP complete.20232m

    Module 5: Tractable and Intractable Problems

    Discuss diagrammatically the relation among $P$ class, $NP$ class, $NP$ hard and $NP$ complete.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8d. Describe Clique Decision Problem (CDP).20232m

    Module 5: Tractable and Intractable Problems

    Describe Clique Decision Problem (CDP).

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8e. Explain the max-flow min-cut theorem with an example.20236m

    Module 4: Graph and Tree Algorithms

    Explain the max-flow min-cut theorem with an example.

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write short notes on: Asymptotic notations20237m

    Module 1: Introduction and Complexity Analysis

    Write short notes on: Asymptotic notations

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write short notes on: Heap creation technique20237m

    Module 2: Divide and Conquer Paradigm and Heaps

    Write short notes on: Heap creation technique

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9c. Write short notes on: Strassen's matrix multiplication20237m

    Module 2: Divide and Conquer Paradigm and Heaps

    Write short notes on: Strassen's matrix multiplication

    View this question on its own page →

    CopySearch GoogleAsk AI
30. Q9d. Write short notes on: Divide-and-Conquer vs Dynamic programming20237m

    Module 3: Greedy, Dynamic Programming and Other Paradigms

    Write short notes on: Divide-and-Conquer vs Dynamic programming

    View this question on its own page →

    CopySearch GoogleAsk AI