Algorithm Design and Analysis
SWE · Final · Spring 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, Spring 2025
Course Code: SE214; Course Title: Algorithm Design and Analysis
Sections & Teachers: FE(A,B,C,N), MRN(D,M), IS(E,F), CP(G,H), NJN(I,J), MMSI(K,L)
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 the key characteristics of Greedy Algorithms and Dynamic Programming in solving optimization problems. [Marks-3] [CLO-3 Level-4]
b) [Figure: a directed weighted graph with nodes 1, 2, 3, 4, 5 showing edges and weights] [Marks-2]
Figure-1 illustrates a directed weighted graph. Represent this graph using an adjacency matrix.
c) You're an AI researcher training a model to detect plagiarism in student essays. As part of the analysis, your algorithm compares different versions of text submissions to detect reused content. You are comparing two versions of a paragraph submitted by a student:
Original Submission: "TRAINING"
Revised Submission: "RATINGS"
To check how much of the content remains unchanged, compute the Longest Common Subsequence (LCS) between the original and the revised submission using dynamic programming. Determine the length of the longest common subsequence and also identify the subsequence itself. [Marks-5]
d) You are robotics engineer programming an autonomous rescue robot. The robot can carry a maximum of 7 kg of equipment during a mission. You have a set of tools, each with a weight and a utility value for rescue operations. Your goal is to maximize the total utility of the tools loaded onto the robot without exceeding the weight limit. Each tool must be fully loaded or not at all.
Tool | Weight | Value
A | 2 | 7
B | 3 | 9
C | 4 | 10
D | 1 | 4
Using a dynamic programming approach, identify the tools to load onto the robot that will maximize the total utility value without going over the 7 kg weight capacity. [Marks-5]
e) You are managing a school fundraising drive, where students can contribute money by placing coins into donation boxes. All of them have coin denominations of BDT {1, 2, 4, 6} for making contributions. A student wants to donate exactly BDT 8 using the fewest number of coins possible. Now, determine the minimum number of coins required to make a total of BDT 8 using dynamic programming and identify which coin denominations can be used to make up that amount. [Marks-5]
2. You are planning to develop a navigation system for your university campus. The campus consists of several buildings connected by walkways. Each walkway has a travel time (in minutes) based on distance or congestion. You are given the following information: From Knowledge Tower - Auditorium takes 5 min, Store - Auditorium: 3 min, Knowledge Tower - Central Field: 7 min, Store - Bonomaya: 4 min, Transport - Bonomaya: 6 min, Central Field - Transport: 8 min, Auditorium - Central Field: 15 min, Auditorium to transport: 15 min [CLO-4 Level-5]
a) Summarize the navigation as an undirected graph and starting from "Knowledge Tower," explore the graph as deeply as possible. Your chosen traversal method requires the data structure Stack. Determine the order in which the nodes are visited based on this strategy. [Marks-6]
b) Explain the process of greedy approach to find the shortest travel time between Auditorium to Transport and also show the shortest path. [Marks-6]
c) You are given the following 15-character message: ABACAAACEEEDDAF
Now answer the following questions.
i) Analyze the given message and figure out the frequency of each distinct character.
ii) 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.
iii) Investigate the total number of bits required for transmitting and decoding the message using Huffman encoding.
iv) Compare the bit-length of the Huffman encoded message with the bit-length required without compression, assuming standard ASCII encoding, where each character is represented using 8 bits. [Marks-8]