Algorithms
CSE · Final · Spring 24
Batch 64
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 and Engineering
Final Term Examination, Spring-2024
Course Code: CSE213 Course Title: Algorithms
Level: 2, Term: 1, Batch: 64
Exam Duration: 2.0 Hours
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. You are given two sequences of characters. Apply an appropriate algorithm to find out the [5] CO2
Longest Common Subsequence of the given sequences (Show detailed simulation step-by-step).
Write down the common subsequence(If there are multiple common subsequences write all of
them)
DAFFODILUNI
DHAKAUNI
2. Tara is a brilliant girl and mostly likes mathematics a lot. One day she and you(her best friend) [6] CO3
were sitting on the couch and counting coins that she saved from her monthly pocket money. She
had mostly 1 taka coin, 2 taka coin, 5 taka coin and 7 taka coin and she has unlimited amounts of
these taka coins. Her father saw that she was counting coins so he came and asked her how many
ways she can make 11 taka using all of these coins. But she alone can't do this calculation. so she
asked for your help as you are a good mathematician. Help her by applying an appropriate
algorithm to find out how many ways you can make 11 taka using 1,2,5 and 7 taka coins (Show
detailed steps).
3. You are given an undirected graph below. Show the detailed steps and find out whether node E is [5] CO2
present in the graph or not by applying Depth First Search(DFS). Start Node: A
[Figure: An undirected graph with nodes A, B, C, D, E, F, G where A is connected to B, C, G; B is connected to A, C, D; C is connected to A, B; D is connected to B, F; E is connected to G, F; F is connected to D, E; G is connected to A, E.]
4. You are given an undirected graph. Convert this graph into a tree by applying the MST [6] CO2
algorithm(Prim's) and show all necessary steps.
[Figure: An undirected weighted graph with nodes A, B, C, D, E, F, G, H with various edge weights.]
5. Mr. Jo Leyung is always short on time. He is currently in courier service and delivers parcels [6] CO3
from door to door. But he loves his family very much. He really wants to find some time for his
family. Only way to find that is to somehow minimize his delivery times. Now for the given graph
between each vertex represents the places he delivers parcels and each edge is the time needed to
reach from one place to another. He wants your help to find out the minimum possible time to
reach from one place to another. As he is unable to inform you of a definite starting point you have
to help him to find the minimum time from any one of the locations to another. Which algorithm
will you choose? Apply the algorithm and show the necessary simulating steps. [Starting node: A]
[Figure: A directed weighted graph with nodes A, B, C, D, E and directed edges with weights between them.]
6. You are given a directed graph. Apply an appropriate algorithm to find the strongly connected [6] CO2
components of the given graph (Show all the necessary steps).
[Figure: A directed graph with nodes A, B, C, D, E, F, G, H, I and directed edges between them.]
7. Imagine you're managing a delivery service in a city with a network of roads connecting various [6] CO3
neighborhoods. Your task is to find the shortest route for a delivery truck to reach its destination
from the distribution center. However, some roads have tolls, while others offer discounts for quick
delivery. The road network is represented as a weighted graph, where the vertices represent
neighborhoods and the edges represent roads between them. The weight of each edge represents
the time it takes to travel that road, including tolls or discounts. However, due to recent policy
changes, some roads now have negative weights, indicating a discount for using them. Your
challenge is to find the shortest path for the delivery truck from the distribution center to its
destination, considering both positive and negative edge weights. Keep in mind that negative edge
weights may lead to opportunities for shortcuts, but they can also introduce complexities such as
the possibility of negative cycles. Apply an appropriate algorithm to find the shortest path from A
to other nodes. [Show necessary steps]
[Figure: A directed weighted graph with nodes A, B, C, D, E, F and directed edges with weights including negative values.]