Skip to content

Algorithms

CSE · Final · Spring 23

Batch 60

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 Department of Computer Science and Engineering Faculty of Science & Information Technology Final Examination, Spring 2023 Course Code: CSE 214, Course Title: Algorithm Level: 2 Term: 1 Batch: 60 Time: 2 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) A man wants to go different places in the world. He has listed them down all. But there are some places where he wants to visit before some other places. Suppose he has started his visit from location A. In the following graph Location (A) before location (B) means there's an edge from A to B. What application of graph can he used to determine that? Suppose the man will start his visiting from A. Now apply the algorithm for the following graph and determine the order of the places he visited one by one. [5] [CO4] [Figure: A directed acyclic graph with nodes A, B, C, D, E, F, G and directed edges between them] b) Apply the appropriate algorithm to find the shortest path from S to other connected nodes [5] [Figure: A weighted undirected graph with nodes S, A, B, C, D, E, F and edge weights] c) Suppose you have the graph to consider and you going to make a Spanning Tree by picking the highest weighted edge before picking the low weighted edge. Now what kind of approach you will use for solving the problem. Apply appropriate algorithm based on the criteria mentioned here. [5] 2. a) Suppose you have a list of ages for a number of students as below. Now list them in an order such that the ages are arranged in Increasing order. Now find the total number of students and the list of the students that support the decreasing order using DP [5] [CO3] A[ ] = [4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3]. b) Suppose your friends ask you to let them know the similarity between your Last name and your mother's first name. Give them the answer by using any algorithm you have learned so far. What type of algorithm did you choose to get the answer? Simulate the appropriate algorithm to find the matching characters. [5] 3. Identify the Tree, Forward, Back and cross edges from the following graph. [5] [CO2] [Figure: A directed graph with nodes s, a, b, c, d and edges] 4. a) Write your five most favorite area names located within 10-kilometer distance from your home. Now using these five points and one extra point for your home location draw an undirected and weighted graph. Weights of all the edges will be the number of times in minutes to go from one point to another point. Here put all possible edges in the graph. Make sure no pair of vertices is left without an edge. Built your graph based on your home location and find the following [5] [CO4] a) Choose the kind of graph have you drawn? b) Identify the adjacency matrix and list for the graph. b) Suppose you have entered a mysterious cave with a knapsack of capacity 10 Kg. You have found the following valuables in the cave: Item Name Diamond Ruby Turquoise Emerald Sapphire [5] Weight (kg) 3 4 3 6 2 Price (in million BDT per kg) 8 3 5 7 6 Here you cannot break any of the items. Either you can take an item entirely or you cannot (0/1). Identify your maximum profit. Solve the total profit and also find which items you will choose?