Design and Analysis of Algorithm Unit 3 Important Questions AKTU

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Unit 3 · Important Question

AKTU Design and Analysis of Algorithm (BCS503) Unit 3 important questions for B.Tech Semester 5 – Divide and Conquer & Greedy Methods. Topics: Divide and…

Open the interactive reader to study this resource on AcademicArk.

Unit 3: Divide and Conquer & Greedy Methods – AKTU syllabus topics

  • Divide and Conquer: Matrix Multiplication, Convex Hull, Searching, Graph Representation
  • Greedy Methods: Knapsack Problem, Optimal Reliability Allocation, Activity Selection Problem
  • Minimum Spanning Trees: Prim's Algorithm, Kruskal's Algorithm
  • Single Source Shortest Paths: Dijkstra's Algorithm, Bellman Ford Algorithm, Depth First Search

Most asked AKTU PYQ questions from Unit 3

  1. Q5b. Explain Dijkstra's Algorithm. Prove that it may fail if the graph contains negative edge weights. (7 marks, 2025-26)
  2. Q4b. Explain Kruskal's algorithm for MST and also discuss time complexity. (7 marks, 2025-26)
  3. Q5a. Write and explain the Kruskal’s algorithm to find Minimum Spanning Tree of a graph with a suitable example. (7 marks, 2024-25)
  4. Q2c. Write and explain the Kruskal algorithm to find the Minimum Spanning Tree of a graph with suitable example. (10 marks, 2021-22)
  5. Q5b. Explain Dijkstra's algorithm to solve single source shortest path problem with suitable example. (10 marks, 2020-21)
  6. Q6a. Write an algorithm of Dijkstra and implement it by taking any example. (10 marks, 2023-24)
  7. Q2c. Prove that if the weights on the edge of the connected undirected graph are distinct then there is a unique Minimum Spanning Tree. Give an example in this regard. Also discuss Kruskal’s Minimum Spanning Tree in detail. (10 marks, 2022-23)
  8. Q2c. Apply the greedy single source shortest path algorithm on the graph given below. (7 marks, 2024-25)
  9. Q5b. Find the optimal solution of the fractional Knapsack problem with n=7 and the knapsack capacity of m=15. The profits and weights of the items are given below. Objects: 1 2 3 4 5 6 7 Profit (P): 5 10 15 7 8 9 4 Weight (w): 1 3 5 4 1 3 2 (7 marks, 2024-25)
  10. Q2c. Define spanning tree. Write Kruskal’s algorithm for finding minimum cost spanning tree. Describe how Kruskal’s algorithm is different from Prim's algorithm for finding minimum cost spanning tree. (7 marks, 2019-20)

AKTU paper codes: BCS503, KCS503, RCS502

Other Design and Analysis of Algorithm units

Design and Analysis of Algorithm previous year papers

More Design and Analysis of Algorithm resources

Browse all notes · Semester 5 notes