Algorithms
CSE · Final · Summer 25
Batch 67
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 Computer Science & Engineering
Final Examination, Summer 2025
Course Code: CSE 213, Course Title: Algorithms
Level:1 Term:3 Batch:67
Time: 02:00 Hrs
Marks: 40
1. a) A charity organization is collecting donations in specific denominations of coins: {1, 3, 6, 7}. You are given an amount A = 8, and your task is to help the organizer determine the minimum number of coins required to make exactly 8 using any number of coins from the given denominations, by applying the Dynamic Programming coin change technique. | 5 | CO2
b) You are developing a tool similar to Google Docs or Git that tracks changes between two versions of a file. To achieve this, your tool needs to find the common parts (subsequence) that remains unchanged. You are given two versions of a document as strings:
- Old version: "ACDFGLM"
- New version: "AEDFLM"
Now Find the length of the Longest Common Subsequence (LCS). | 5 | CO2
2. a) s is in a large building with many interconnected rooms. She wants to explore all of them. She starts from her current room, visits all the rooms directly connected to it first, then moves on to the rooms connected to those, and continues in this way— step by step, level by level. Apply the appropriate graph searching algorithm to explore the rooms and write down the order of traversal for the given graph
[Figure: a graph with nodes s, e, r, t, q, P, g] | 5 | CO2
b) a has just joined a social network. She starts exploring her friend circle by checking her direct friends, then her friends' friends, and so on. She continues to go deeper into each connection before coming back and checking others. Apply the appropriate graph searching algorithm to explore her friend circle and write down the order of traversal for the given graph. | 5 | CO2
[Figure: a directed graph with nodes a, b, c, d, e, f, g, h]
3. a) Z is organizing a series of workshops. Some workshops must be completed before others. For example:
- Workshop "0" must be done before workshop "3"
- Workshop "4" and "2" must be done before Workshop "1"
She wants to determine a proper order to arrange all the workshops so that each workshop is scheduled after all its prerequisites have been completed. From the given graph, find one valid order in which Z can arrange the workshops. | 6 | CO3
[Figure: a directed acyclic graph with nodes 0, 1, 2, 3, 4, 5]
b) X is an engineer building a network of roads to connect all the villages in a region. Every village is already connected to some others by possible road paths, and each path has a construction cost. She wants to connect all villages so that the total construction cost is as low as possible. She starts building roads from one village(A) and keeps adding the cheapest possible connection to a village that hasn't been connected yet. Find the Minimum Spanning Tree of the given graph. | 7 |
[Figure: a weighted undirected graph with nodes A, B, C, D, E, F, G, H]
c) A works in a courier company. She wants to calculate the minimum delivery cost from the main office to all other branches. Each delivery route has a cost, but some branches offer discounts that reduce the total cost when packages pass through them. To make sure she's getting the lowest cost, she checks all routes again and again, updating the cost if she finds a cheaper way through another branch. From source A, find the shortest path to all other nodes using the proper algorithm. | 7 |
[Figure: a weighted directed graph with nodes A, B, C, D, E, F with negative edge weights]