Skip to content

Algorithm Design and Analysis

SWE · Final · Spring 26

Paper 1 of 4By MAHMUDUL HASANSwitch

Paper 1 of 4

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, Spring 2026 Course Code: SE214; Course Title: Algorithm Design and Analysis Sections & Teachers: SA(A,B,C), IS(D,H), FE(E,F,G), MMSI(I,J), SSI(K,L), AF(M,N), AG(O) 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) Compare Greedy algorithms and Dynamic Programming in terms of how they use optimal substructure and overlapping subproblems to achieve optimal solutions. [Marks-2] [CLO-3 Level-4] 1. b) A research team is preparing a survival backpack for a week-long expedition into a remote rainforest. The backpack can carry a maximum weight of 7 kg. The team has identified several essential items, each with a weight and a "survival importance score" that reflects how useful the item is during the trip. [Marks-6] Item | Description | Weight (Kg) | Importance Value A | Tent | 4 | 40 B | First-Aid Kit | 3 | 30 C | Food Supplies | 2 | 50 D | Water Filter | 1 | 20 E | Flashlight | 1 | 10 F | Rope | 1 | 15 i. Select the best combination of items to include in the backpack so that (constraint is either you can select the item or not) the total importance value is maximized. ii. Explain why the ratio approach won't give an optimal solution for this problem. 1. c) A bioinformatics system is comparing two short DNA-like sequences to detect conserved regions. The sequences are deliberately mutated, making the common subsequence hard to see by inspection. The sequences are: X = A C G T A C G Y = G A C A G T C [Marks-6] i. Identify the common subsequence with maximum possible length showing the approach and traceback path. ii. Analyze if this problem has multiple solutions or not, if yes then explain why multiple valid LCS sequences may exist in this case. 1. d) Analyze how dynamic programming can be used to determine the total number of ways to form a given amount using available coin denominations, assuming each coin can be used multiple times. Coins = [1, 2, 3, 5] Amount = 6 [Marks-6] 2. a) Using Prim's algorithm, determine the Minimum Spanning Tree (MST) of the given graph, starting from vertex A. Show all steps and justify why the final structure satisfies the properties of an MST. [Figure: A connected undirected graph with vertices A, B, C, D, E, F, G, H and weighted edges: A-B (14), A-C (9), A-D (15), B-C (2), B-D (14), B-E (20), B-F (13), B-H (26), C-D (12), C-E (12), D-E (10), E-F (10), E-G (14), E-H (33), F-G (21), F-H (5), G-H (7)] [Marks-6] [CLO-4 Level-5] 2. b) A cloud storage service provider is trying to optimize how text data is stored and transmitted between its distributed servers. Due to high bandwidth expenses, the company is charged based on the number of bits used during transmission, where each bit costs 1 Taka. To reduce this cost, the system engineer decides to apply an efficient data compression technique that assigns shorter binary codes to more frequent characters and longer codes to less frequent ones. The following data needs to be processed and transmitted: aaaaaaaaabbbbbbtccccccdddddeeeeffgg [Marks-8] i. Determine the Huffman tree and generate the corresponding codes for each character. ii. Select the appropriate codes to encode the entire data string. iii. Measure the total transmission cost if 1 bit = 1 Taka. iv. Estimate the original transmission cost without compression, assuming 1 character = 8 bits. 2. c) Consider the following graph, and determine the shortest path using an appropriate algorithm. [Figure: A directed graph with vertices A, B, C, D, E and weighted edges: A-B (6), A-C (5), B-C (-2), B-D (-1), C-E (3), D-C (4), D-E (3)] [Marks-6]