Skip to content

Algorithms

CSE · Final · Spring 24

Batch 64

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 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.]