Algorithm Design and Analysis
SWE · Final · Summer 25
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Department of Software Engineering
Faculty of Science & Information Technology
Final Examination, Summer 2025
Course Code: SE214; Course Title: Algorithm Design and Analysis
Sections & Teachers: FE(A, B, C), MHS(D), CP(E), AJE(F, G), MMSI(H, I), AF(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) Differentiate between a graph and a tree by explaining their key differences in structure and properties. [Marks-3] CLO-3 Level-4
1. b) Explain how BFS and DFS visit nodes in a graph differently, and mention which one is better for finding the shortest path in an unweighted graph. [Marks-3]
1. c) You are given two sequences of genetic markers from two patients. Apply an appropriate algorithm to determine the Longest Common Subsequence (LCS) between the given sequences and show the detailed simulation step-by-step. Identify one of the longest common subsequences. [Marks-7]
Sequence 1: ACGTGTA
Sequence 2: GCTAGTA
1. d) You are preparing for a hiking trip and have 5 items to pack. Each item has a weight (in kilograms) and a usefulness rating. Your backpack can carry up to 7 kilograms. You want to maximize the total usefulness of the items you pack without exceeding the weight limit. You must either take the whole item or leave it (no partial packing). [Marks-7]
Item Name | Weight(Kg) | Usefulness
Hiking Boots | 4 | 8
Water Bottle | 3 | 7
Trail Map | 1 | 5
First Aid Kit | 2 | 6
Portable Stove | 5 | 9
Using a dynamic programming approach, determine which hiking items should be packed into a backpack with a maximum weight capacity of 7 kg to maximize the total usefulness value.
2. a) As part of the university's tech innovation challenge, you are tasked with creating a walking-route planner that finds the quickest path between campus locations. The campus has: Library (L), Laboratory (Lab), Administration (A), Central Garden (CG), Gym (G), Cafeteria (C), and Bookstore (B).These locations are connected by walkways, and the travel times (in minutes) between them are affected by distance and foot traffic. You are given the following information:
From the Library, it takes 4 minutes to walk to the Laboratory and 6 minutes to the Administration Office. The Laboratory is connected to the Gym in 5 minutes and to the Cafeteria in 8 minutes. The Administration Office is 3 minutes from the Cafeteria and 2 minutes from the Central Garden. Walking from the Central Garden to the Gym takes 4 minutes, and from the Gym to the Cafeteria takes 6 minutes. The Cafeteria is 7 minutes from the Bookstore, while the Central Garden is 5 minutes from the Bookstore.
Determine the shortest path and total travel time from the Library (L) to the Bookstore (B) using Dijkstra's algorithm by showing step by step implementation on the weighted graph constructed using the given information. [Marks-7] CLO-4 Level-5
2. b) Determine the Minimum Spanning Tree (MST) of the given undirected, weighted graph using Prim's algorithm, showing each step until the minimum total cost is obtained. Also, justify why it is called a Minimum Spanning Tree in the context of graph theory. [Marks-6]
[Figure: An undirected weighted graph with vertices a, b, c, d, e, f, g, h and edges with weights connecting them.]
2. c) You are given a 20-character message. The frequency of each letter in that message is listed below:
E- 1
N- 3
C- 4
R- 1
Y- 2
P- 5
T- 4
Now answer the following questions.
i) Illustrate a Huffman tree and assign variable-length binary codes, ensuring that characters with higher frequencies get shorter codes and those with lower frequencies get longer codes.
ii) Investigate the total number of bits required for transmitting and decoding the message using Huffman encoding.
iii) Compare the bit-length of the Huffman encoded message with the bitlength required without compression, assuming standard ASCII encoding, where each character is represented using 8 bits. [Marks-7]