Skip to content

Algorithm Design and Analysis

SWE · Final · Summer 26

Paper 3 of 6By Jobayer Ahmed Usamah - SWE (251)Switch

Paper 3 of 6

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

Read the questions as text

Read off the PDF by AI, so it may have mistakes. The PDF is the original.

Daffodil International University Faculty of Science & Information Technology Department of Software Engineering Final Examination, Summer 2026 Course Code: SE214; Course Title: Algorithm Design and Analysis Sections & Teachers: AS (A, B, C), MMSI (D, E), AAS (F, G), AF (H, I), SA (J) Time: 2:00 Hrs Marks: 40 Answer ALL Questions [The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.] 1. a) Analyze the given graph and illustrate its linked (adjacency list) and sequential (adjacency matrix) representations. [Figure: A graph with nodes A, B, C, D, E connected with directed/undirected edges] [Marks: 1.5+1.5] 1. b) An emergency relief drone can carry a maximum of 9 kg of supplies. The available items are: Item | Emergency Supply | Weight (kg) | Priority Value A | Medicine Kit | 2 | 30 B | Food Pack | 3 | 40 C | Water Pack | 4 | 45 D | Rescue Equipment | 5 | 80 The relief coordinator plans to load items A, B, and C, claiming that their combined priority value of 115 makes this the best possible selection. (i) Optimize the selection of emergency supplies using the 0/1 Knapsack approach and identify the combination that provides the maximum priority value. (ii) Compare the optimal solution obtained in part (i) with the coordinator's proposed selection of A, B, and C, and explain whether the coordinator's decision is optimal based on the total weight and priority value. [Marks: 5+2] CLO 3 Level 4 1. c) A digital publishing company is comparing two product names after a branding update to determine the longest sequence of unchanged characters. Since the names have been partially modified, the system uses the Longest Common Subsequence (LCS) algorithm to identify the shared pattern. The two names are X = PLATFORM Y = PLASTRON (i) Identify the common subsequence with the maximum possible length, showing the approach and traceback path. (ii) Analyze how the dynamic programming table helps avoid redundant computations compared to a recursive solution. [Marks: 4+1] 1. d) A vending machine is programmed to dispense change using the minimum number of coins to reduce dispensing time and improve efficiency. The machine has an unlimited supply of coins with the following denominations: [1, 2, 5, 8] A customer needs to receive 10 units of change. Analyze how dynamic programming can be used to determine the minimum number of coins required to dispense the change, assuming each coin denomination can be used multiple times. [Marks: 5] 2. a) A warehouse needs to pack the following items into bins of capacity 10 units: Item | Size A | 8 B | 3 C | 6 D | 4 E | 7 F | 2 Evaluate the First-Fit and First-Fit Decreasing approaches for the given items and determine which provides the more optimized solution. [Marks: 5] 2. b) Consider the weighted graph shown below. [Figure: A complex graph with nodes n00, n01, n02, n03, n04, s, t and various edge weights like 8,033, 6,263, 5,840, 4,183, 4,417, 6,661, 4,929, 8,824, 741, 6,932, 6,518, 5,566, 4,923, 8,471] A student applies Kruskal's algorithm and selects the following edges to construct a minimum spanning tree (MST): (n02, n03), (n04, n01), (s, n04), (n00, t), (n03, t), (n00, n04) The student claims that the resulting tree is the minimum spanning tree. Evaluate whether the selected edges form a valid minimum spanning tree (MST). If any selected edge is incorrect, identify the error(s), construct the correct MST, and calculate its total weight. Justify your answer with appropriate reasoning. [Marks: 2+5] CLO 4 Level 5 2. c) Determine the shortest paths from the given source vertex (S) to all other vertices using the Bellman-Ford algorithm. [Figure: A directed graph with source vertex S, vertices A, B, C, D, t and weighted edges with values 1, 3, 4, -1, 5, 2, -2, 1, 4] [Marks: 8]