2025 question paper
Design and Analysis of Algorithms
28 questions
Q1a. Which property of an algorithm ensures that every step is clear and has exactly one meaning? (i) Finiteness (ii) Effectiveness (iii) Definiteness (iv) Generality20252m
Module 1: Introduction
View this question on its own page →Which property of an algorithm ensures that every step is clear and has exactly one meaning?
(i) Finiteness
(ii) Effectiveness
(iii) Definiteness
(iv) GeneralityQ1b. In Asymptotic notation, Big- \Omega (Omega) is used to represent (i) The upper bound (Worst-case) (ii) The lower bound (Best-case) (iii) The tight bound (Average-case) (iv) None of the above20252m
Module 1: Introduction
View this question on its own page →In Asymptotic notation, Big- (Omega) is used to represent
(i) The upper bound (Worst-case)
(ii) The lower bound (Best-case)
(iii) The tight bound (Average-case)
(iv) None of the aboveQ1c. A FIFO Branch-and-Bound strategy is typically implemented using which data structure? (i) Stack (ii) Queue (iii) Priority Queue (iv) Array20252m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →A FIFO Branch-and-Bound strategy is typically implemented using which data structure?
(i) Stack
(ii) Queue
(iii) Priority Queue
(iv) ArrayQ1d. The 0/1 Knapsack problem is traditionally solved using which approach to ensure an optimal solution? (i) Greedy Method (ii) Dynamic Programming (iii) Brute-Force only (iv) Linear Search20252m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →The 0/1 Knapsack problem is traditionally solved using which approach to ensure an optimal solution?
(i) Greedy Method
(ii) Dynamic Programming
(iii) Brute-Force only
(iv) Linear SearchQ1e. In an unweighted graph, which algorithm is guaranteed to find the shortest path between two nodes? (i) Depth First Search (ii) Kruskal's Algorithm (iii) Breadth First Search (iv) Prim's Algorithm20252m
Module 3: Graph and Tree Algorithms
View this question on its own page →In an unweighted graph, which algorithm is guaranteed to find the shortest path between two nodes?
(i) Depth First Search
(ii) Kruskal's Algorithm
(iii) Breadth First Search
(iv) Prim's AlgorithmQ1f. Which of the following algorithms is commonly used to find the Minimum Spanning Tree of a graph? (i) Dijkstra's Algorithm (ii) Kruskal's Algorithm (iii) Bellman-Ford Algorithm (iv) Floyd-Warshall Algorithm20252m
Module 3: Graph and Tree Algorithms
View this question on its own page →Which of the following algorithms is commonly used to find the Minimum Spanning Tree of a graph?
(i) Dijkstra's Algorithm
(ii) Kruskal's Algorithm
(iii) Bellman-Ford Algorithm
(iv) Floyd-Warshall AlgorithmQ1g. If all edge weights in a graph are positive, what is the minimum number of edges in a spanning tree for a graph with vertices? (i) V (ii) V-1 (iii) V+1 (iv) 2V20252m
Module 3: Graph and Tree Algorithms
View this question on its own page →If all edge weights in a graph are positive, what is the minimum number of edges in a spanning tree for a graph with vertices?
(i) V
(ii) V-1
(iii) V+1
(iv) 2VQ1h. Which complexity class contains problems for which a given solution can be verified in polynomial time by a deterministic Turing machine? (i) Class P (ii) Class NP (iii) Class NP-Hard (iv) Class Undecidable20252m
Module 4: Tractable and Intractable Problems
View this question on its own page →Which complexity class contains problems for which a given solution can be verified in polynomial time by a deterministic Turing machine?
(i) Class P
(ii) Class NP
(iii) Class NP-Hard
(iv) Class UndecidableQ1i. What is the approximation ratio (or performance ratio) of the greedy algorithm for the Vertex Cover problem? (i) 2 (ii) 1.5 (iii) ln n (iv) 120252m
Module 5: Advanced Topics
View this question on its own page →What is the approximation ratio (or performance ratio) of the greedy algorithm for the Vertex Cover problem?
(i) 2
(ii) 1.5
(iii) ln n
(iv) 1Q1j. The Quantified Boolean Formula problem is a canonical complete problem for which of the following complexity classes? (i) NP (ii) P (iii) PSPACE (iv) co-NP20252m
Module 4: Tractable and Intractable Problems
View this question on its own page →The Quantified Boolean Formula problem is a canonical complete problem for which of the following complexity classes?
(i) NP
(ii) P
(iii) PSPACE
(iv) co-NPQ2a. Write and explain the Cook's theorem.20257m
Module 4: Tractable and Intractable Problems
View this question on its own page →Write and explain the Cook's theorem.
Q2b. Define time complexity and space complexity. Write an algorithm for adding n natural numbers and find the space required by that algorithm.20257m
Module 1: Introduction
View this question on its own page →Define time complexity and space complexity. Write an algorithm for adding n natural numbers and find the space required by that algorithm.
Q3a. Discuss the concepts of asymptotic notations and its properties.20257m
Module 1: Introduction
View this question on its own page →Discuss the concepts of asymptotic notations and its properties.
Q3b. What is a Minimum Cost Spanning tree? Explain Kruskal's Minimum cost spanning tree algorithm with a suitable example.20257m
Module 3: Graph and Tree Algorithms
View this question on its own page →What is a Minimum Cost Spanning tree? Explain Kruskal's Minimum cost spanning tree algorithm with a suitable example.
Q4a. Find an optimal solution to the knapsack instance n=4 objects and the capacity of knapsack m=15, profits are (10, 5, 7, 11) and weights are (3, 4, 3, 5).20257m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →Find an optimal solution to the knapsack instance objects and the capacity of knapsack , profits are and weights are .
Q4b. Compare NP-hard and NP-completeness?20257m
Module 4: Tractable and Intractable Problems
View this question on its own page →Compare NP-hard and NP-completeness?
Q5a. Explain BFS algorithm in detail. Also explain its time complexity.20257m
Module 3: Graph and Tree Algorithms
View this question on its own page →Explain BFS algorithm in detail. Also explain its time complexity.
Q5b. Explain how Bellman Ford algorithm can be used to detect the presence of negative weight cycles.20257m
Module 3: Graph and Tree Algorithms
View this question on its own page →Explain how Bellman Ford algorithm can be used to detect the presence of negative weight cycles.
Q6a. Explain the Prim's algorithm. What is the time complexity of Prim's algorithm?20257m
Module 3: Graph and Tree Algorithms
View this question on its own page →Explain the Prim's algorithm. What is the time complexity of Prim's algorithm?
Q6b. Apply the Prim's algorithm and find the optimal solution for the following graph: 20257m
Module 3: Graph and Tree Algorithms
View this question on its own page →Apply the Prim's algorithm and find the optimal solution for the following graph:
Q7a. Explain the approximation algorithm for the travelling salesman problem.20257m
Module 5: Advanced Topics
View this question on its own page →Explain the approximation algorithm for the travelling salesman problem.
Q7b. Discuss the steps to find approximate solutions to NP-Hard optimization problems using approximation algorithms with an example.20257m
Module 5: Advanced Topics
View this question on its own page →Discuss the steps to find approximate solutions to NP-Hard optimization problems using approximation algorithms with an example.
Q8a. Explain the Brute Force method of algorithm design with suitable examples.20257m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →Explain the Brute Force method of algorithm design with suitable examples.
Q8b. Explain the Bin Packing Problem using heuristic techniques such as: * First Fit * Best Fit * Next Fit20257m
Module 5: Advanced Topics
View this question on its own page →Explain the Bin Packing Problem using heuristic techniques such as:
- First Fit
- Best Fit
- Next Fit
Q9a. Write a short note on: Heuristics characteristics and their application domains.20257m
Module 5: Advanced Topics
View this question on its own page →Write a short note on:
Heuristics characteristics and their application domains.
Q9b. Write a short note on: Recursion tree method20257m
Module 1: Introduction
View this question on its own page →Write a short note on:
Recursion tree method
Q9c. Write a short note on: Dynamic Programming20257m
Module 2: Fundamental Algorithmic Strategies
View this question on its own page →Write a short note on:
Dynamic Programming
Q9d. Write a short note on: Asymptotic Notations20257m
Module 1: Introduction
View this question on its own page →Write a short note on:
Asymptotic Notations