2024 question paper
Design and Analysis of Algorithms
26 questions
Q1a. Which of the following best describes space complexity? (i) Time taken by the algorithm (ii) Memory required to run an algorithm (iii) Number of recursive calls (iv) Number of loops used20242m
Module 1: Introduction
View this question on its own page →Which of the following best describes space complexity?
(i) Time taken by the algorithm
(ii) Memory required to run an algorithm
(iii) Number of recursive calls
(iv) Number of loops usedQ1b. If an algorithm has time complexity T(n) = 5n^2 + 3n + 7, its asymptotic upper bound is: (i) O(n) (ii) O(n^2) (iii) O(n \log n) (iv) O(n^3)20242m
Module 1: Introduction
View this question on its own page →If an algorithm has time complexity , its asymptotic upper bound is:
(i)
(ii)
(iii)
(iv)Q1c. The recurrence T(n) = T(n/2) + 1 has a time complexity of: (i) O(n) (ii) O(\log n) (iii) O(n \log n) (iv) O(n^2)20242m
Module 1: Introduction
View this question on its own page →The recurrence has a time complexity of:
(i)
(ii)
(iii)
(iv)Q1d. Which strategy solves problems by solving subproblems and combining their solutions? (i) Brute Force (ii) Greedy (iii) Dynamic Programming (iv) Backtracking20242m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →Which strategy solves problems by solving subproblems and combining their solutions?
(i) Brute Force
(ii) Greedy
(iii) Dynamic Programming
(iv) BacktrackingQ1e. In DFS traversal of a graph, which data structure is used to keep track of visited nodes? (i) Queue (ii) Stack (iii) Priority Queue (iv) Heap20242m
Module 3: Graph and Tree Algorithms
View this question on its own page →In DFS traversal of a graph, which data structure is used to keep track of visited nodes?
(i) Queue
(ii) Stack
(iii) Priority Queue
(iv) HeapQ1f. Which algorithm is used to find a Minimum Spanning Tree? (i) Dijkstra's algorithm (ii) Prim's algorithm (iii) Bellman-Ford algorithm (iv) Floyd-Warshall algorithm20242m
Module 3: Graph and Tree Algorithms
View this question on its own page →Which algorithm is used to find a Minimum Spanning Tree?
(i) Dijkstra's algorithm
(ii) Prim's algorithm
(iii) Bellman-Ford algorithm
(iv) Floyd-Warshall algorithmQ1g. Topological sorting is only possible in: (i) Undirected Graphs (ii) Trees (iii) Directed Acyclic Graphs (iv) Weighted Graphs20242m
Module 3: Graph and Tree Algorithms
View this question on its own page →Topological sorting is only possible in:
(i) Undirected Graphs
(ii) Trees
(iii) Directed Acyclic Graphs
(iv) Weighted GraphsQ1h. Which algorithm is typically used in maximum flow problems? (i) Kruskal's Algorithm (ii) Floyd-Warshall (iii) Ford-Fulkerson (iv) Prim's Algorithm20242m
Module 3: Graph and Tree Algorithms
View this question on its own page →Which algorithm is typically used in maximum flow problems?
(i) Kruskal's Algorithm
(ii) Floyd-Warshall
(iii) Ford-Fulkerson
(iv) Prim's AlgorithmQ1i. What is the primary technique used to prove that a problem is NP-complete? (i) Divide and conquer (ii) Dynamic programming (iii) Polynomial-time reduction from a known NP-complete problem (iv) Space complexity calculation20242m
Module 4: Tractable and Intractable Problems
View this question on its own page →What is the primary technique used to prove that a problem is NP-complete?
(i) Divide and conquer
(ii) Dynamic programming
(iii) Polynomial-time reduction from a known NP-complete problem
(iv) Space complexity calculationQ1j. Randomized algorithms make use of: (i) Deterministic input (ii) Random choices during execution (iii) Recursive backtracking (iv) Fixed input-output pairs20242m
Module 5: Advanced Topics
View this question on its own page →Randomized algorithms make use of:
(i) Deterministic input
(ii) Random choices during execution
(iii) Recursive backtracking
(iv) Fixed input-output pairsQ2a. Answer the following: (i) Differentiate between best-case, worst-case, and average-case complexity with suitable examples. (ii) Use examples like linear search to demonstrate the differences. (iii) Discuss why worst-case analysis is often preferred in practice.20247m
Module 1: Introduction
View this question on its own page →Answer the following:
(i) Differentiate between best-case, worst-case, and average-case complexity with suitable examples.
(ii) Use examples like linear search to demonstrate the differences.
(iii) Discuss why worst-case analysis is often preferred in practice.Q2b. Suppose the number of basic operations in an algorithm is defined as: T(n) = T(n-1) + n, with T(1) = 1. Solve this recurrence using the substitution method and determine the time complexity.20247m
Module 1: Introduction
View this question on its own page →Suppose the number of basic operations in an algorithm is defined as: , with .
Solve this recurrence using the substitution method and determine the time complexity.Q3a. What is the Master's Theorem? State the general form and the three cases of the theorem. Use it to solve the following recurrence relations: (i) T(n) = 2T(n/2) + n (ii) T(n) = 3T(n/2) + n^2 (iii) T(n) = 2T(n/2) + n/\log n Explain which case applies in each situation.20247m
Module 1: Introduction
View this question on its own page →What is the Master's Theorem? State the general form and the three cases of the theorem. Use it to solve the following recurrence relations:
(i)
(ii)
(iii)
Explain which case applies in each situation.Q3b. Answer the following: (i) Compare dynamic programming and greedy algorithms in terms of their problem-solving approaches, solution spaces, and efficiency. (ii) Discuss scenarios where dynamic programming is necessary because greedy strategies fail. Use suitable problem examples to support your explanation. (iii) Explain how overlapping subproblems and optimal substructure are utilized in dynamic programming.20247m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →Answer the following:
(i) Compare dynamic programming and greedy algorithms in terms of their problem-solving approaches, solution spaces, and efficiency.
(ii) Discuss scenarios where dynamic programming is necessary because greedy strategies fail. Use suitable problem examples to support your explanation.
(iii) Explain how overlapping subproblems and optimal substructure are utilized in dynamic programming.Q4a. The 0/1 Knapsack Problem is a classical combinatorial optimization problem. Explain how this problem can be solved using: (i) Brute-force method (ii) Greedy method (iii) Dynamic Programming (iv) Branch-and-Bound For each approach, explain the algorithm, time complexity, and limitations. Highlight why the greedy method may not always yield the optimal solution.20247m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →The 0/1 Knapsack Problem is a classical combinatorial optimization problem. Explain how this problem can be solved using:
(i) Brute-force method
(ii) Greedy method
(iii) Dynamic Programming
(iv) Branch-and-Bound
For each approach, explain the algorithm, time complexity, and limitations. Highlight why the greedy method may not always yield the optimal solution.Q4b. Consider a TSP with 4 cities A, B, C, D and the following distance matrix: | | A | B | C | D | |---|---|---|---|---| | A | 0 | 10 | 15 | 20 | | B | 10 | 0 | 35 | 25 | | C | 15 | 35 | 0 | 30 | | D | 20 | 25 | 30 | 0 | Answer the following: (i) Use the branch-and-bound algorithm to find the shortest possible route that visits all cities exactly once and returns to the starting city. (ii) Show the branching steps and calculate lower bounds for each partial solution. (iii) Identify how the bounding helps prune the search tree.20247m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →Consider a TSP with 4 cities A, B, C, D and the following distance matrix:
A B C D A 0 10 15 20 B 10 0 35 25 C 15 35 0 30 D 20 25 30 0 Answer the following:
(i) Use the branch-and-bound algorithm to find the shortest possible route that visits all cities exactly once and returns to the starting city.
(ii) Show the branching steps and calculate lower bounds for each partial solution.
(iii) Identify how the bounding helps prune the search tree.Q5a. Answer the following: (i) Compare and contrast the BFS and DFS traversal techniques in terms of their algorithmic approach, time complexity, data structures used, and typical applications. (ii) Give examples where one is preferred over the other.20247m
Module 3: Graph and Tree Algorithms
View this question on its own page →Answer the following:
(i) Compare and contrast the BFS and DFS traversal techniques in terms of their algorithmic approach, time complexity, data structures used, and typical applications.
(ii) Give examples where one is preferred over the other.Q5b. Design a system that finds the shortest paths between various locations in a city. The locations and roads are represented using a graph. What algorithm would you use if: (i) All roads have equal length (ii) Roads have varying lengths, but no negative lengths (iii) Some roads have negative lengths Justify your choices with suitable algorithms and reasoning.20247m
Module 3: Graph and Tree Algorithms
View this question on its own page →Design a system that finds the shortest paths between various locations in a city. The locations and roads are represented using a graph. What algorithm would you use if:
(i) All roads have equal length
(ii) Roads have varying lengths, but no negative lengths
(iii) Some roads have negative lengths
Justify your choices with suitable algorithms and reasoning.Q6a. A graph with five nodes is represented using the adjacency list as follows: | | | | | | |---|---|---|---|---| | A | -> | B (10) | C (3) | | | B | -> | C (1) | D (5) | | | C | -> | B (4) | D (8) | E (2) | | D | -> | E (7) | | | | E | -> | D (9) | | | Answer the following: (i) Draw the graph for the above adjacency list. (ii) Write the algorithm for the Breadth-First Traversal (BFS). (iii) Show the BFS traversal of the graph with the starting node as A.20247m
Module 3: Graph and Tree Algorithms
View this question on its own page →A graph with five nodes is represented using the adjacency list as follows:
A -> B (10) C (3) B -> C (1) D (5) C -> B (4) D (8) E (2) D -> E (7) E -> D (9) Answer the following:
(i) Draw the graph for the above adjacency list.
(ii) Write the algorithm for the Breadth-First Traversal (BFS).
(iii) Show the BFS traversal of the graph with the starting node as A.Q6b. Write the Pseudo-code for the Dijkstra's Algorithm. Further, find the single source (A) shortest path on the following graph: 20247m
Module 3: Graph and Tree Algorithms
View this question on its own page →Write the Pseudo-code for the Dijkstra's Algorithm. Further, find the single source (A) shortest path on the following graph:
Q7a. Answer the following: (i) Explain the concept of a Minimum Spanning Tree (MST) in a connected, weighted, undirected graph. (ii) Compare and contrast Prim's and Kruskal's algorithms for finding the MST. (iii) Analyze the time complexity of both algorithms and discuss their advantages and scenarios where one is preferred over the other.20247m
Module 3: Graph and Tree Algorithms
View this question on its own page →Answer the following:
(i) Explain the concept of a Minimum Spanning Tree (MST) in a connected, weighted, undirected graph.
(ii) Compare and contrast Prim's and Kruskal's algorithms for finding the MST.
(iii) Analyze the time complexity of both algorithms and discuss their advantages and scenarios where one is preferred over the other.Q7b. Given the flow network below with capacities: | EDGE | CAPACITY | |---|---| | S -> A | 10 | | S -> C | 10 | | A -> B | 4 | | A -> C | 2 | | C -> D | 9 | | B -> T | 10 | | D -> B | 6 | | D -> T | 10 | Answer the following: (i) Use the Ford-Fulkerson algorithm to find the maximum flow from source (S) to sink (T). (ii) Show the augmenting paths selected, the bottleneck capacities on each path, and the updated residual capacities after each augmentation. (iii) Calculate the final maximum flow value.20247m
Module 3: Graph and Tree Algorithms
View this question on its own page →Given the flow network below with capacities:
EDGE CAPACITY S -> A 10 S -> C 10 A -> B 4 A -> C 2 C -> D 9 B -> T 10 D -> B 6 D -> T 10 Answer the following:
(i) Use the Ford-Fulkerson algorithm to find the maximum flow from source (S) to sink (T).
(ii) Show the augmenting paths selected, the bottleneck capacities on each path, and the updated residual capacities after each augmentation.
(iii) Calculate the final maximum flow value.Q8a. Answer the following: (i) Describe complexity classes P, NP, NP-complete, and NP-hard. (ii) State and explain Cook's Theorem. (iii) Why is it considered a foundational result in computational complexity theory?20247m
Module 4: Tractable and Intractable Problems
View this question on its own page →Answer the following:
(i) Describe complexity classes P, NP, NP-complete, and NP-hard.
(ii) State and explain Cook's Theorem.
(iii) Why is it considered a foundational result in computational complexity theory?Q8b. Answer the following: (i) What is polynomial-time reduction? (ii) How is it used to prove that a problem is NP-complete? (iii) Explain the process of reducing 3-SAT to Vertex Cover.20247m
Module 4: Tractable and Intractable Problems
View this question on its own page →Answer the following:
(i) What is polynomial-time reduction?
(ii) How is it used to prove that a problem is NP-complete?
(iii) Explain the process of reducing 3-SAT to Vertex Cover.Q9a. Answer the following: (i) Describe randomized algorithms. (ii) Write the algorithm for randomized quick sort. (iii) Give the time complexity of randomized quick sort.20247m
Module 5: Advanced Topics
View this question on its own page →Answer the following:
(i) Describe randomized algorithms.
(ii) Write the algorithm for randomized quick sort.
(iii) Give the time complexity of randomized quick sort.Q9b. Write short notes on the following: (i) Approximation algorithms. (ii) Why are they important in the context of NP-hard optimization problems? (iii) Describe how approximation algorithms can be applied to the Vertex Cover problem.20247m
Module 5: Advanced Topics
View this question on its own page →Write short notes on the following:
(i) Approximation algorithms.
(ii) Why are they important in the context of NP-hard optimization problems?
(iii) Describe how approximation algorithms can be applied to the Vertex Cover problem.