Skip to content

Algorithms

CSE · Final · Spring 25

Batch 66

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-2025 Course Code: CSE213 Course Title: Algorithms Level: 2, Term: 1, Batch: 66 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 | Apply dynamic programming to calculate the total number of possible ways to obtain the given amount using the available coin denominations, with each coin usable multiple times. * Coins = [1, 5, 6, 8] * Amount = 11 | [6] | CO2 2 | You are tasked with comparing two versions of a document in a version control system. To detect the similarities between these two versions, you need to find the Longest Common Subsequence (LCS), which is the longest sequence of characters that appears in both versions, maintaining their relative order. Given the following two versions of a text document: * Version 1: "IPNRFQANT"; * Version 2: "INYFASNT"; Now, Apply an appropriate algorithm to construct the length of the LCS between the two versions and identify the actual LCS (longest common subsequence). | [5] | CO3 3 | You are given a flight network represented as a graph with cities labeled A to I. The connections between cities are given in the diagram below. A traveler wants to explore the cities starting from a given city, always going as deep as possible. Apply an appropriate algorithm and write the order in which the traveler visits the cities. The traveler will start from city "A" and the traveler will not visit a city twice. [Figure: A graph with nodes A, B, C, D, E, F, G, H, I connected by edges] | [5] | CO2 4 | At Daffodil International University, students follow a structured daily routine, navigating between different locations on campus. Your journey starts at the Dormitory (D), where you either proceed to the Food Court (F) for breakfast or the Gym (G) for exercise. you then attend lectures in the Classroom (C), study in the Library (L), and relax in the Common Room (R) before returning to the Dormitory. The travel times between these locations are as follows: D -> F (10 minutes), D -> G (12 minutes), F -> C (5 minutes), G -> C (8 minutes), C -> L (20 minutes), and L -> R (10 minutes). Your task is to construct a directed graph based on the given locations and dependencies and apply Topological Sort to determine a valid sequence for visiting these places and calculate the total time required for the possible path. | [7] | CO3 5 | A delivery company is setting up its fastest and most cost-efficient delivery routes between seven warehouse hubs (A to G) in a city. The company wants to ensure that all warehouses are connected with the minimum total road construction cost. However, the company faces a specific constraint: * Each new road project requires separate government approval, meaning they prefer working on one section at a time rather than evaluating all possible roads at once. * They already have a main distribution hub, so they want to expand from this hub gradually, connecting the most cost-effective roads first rather than sorting through all roads upfront. Decide whether Prim's or Kruskal's algorithm is better suited for this delivery network scenario. Why choose Prim's or Kruskal's? Apply the chosen algorithm step-by-step to find the Minimum Spanning Tree (MST). [Figure: A weighted graph with nodes A, B, C, D, E, F, G and edge weights] | [6] | CO3 6 | Given an array of positive integers, write a pseudocode to find the second largest element from the array. | [4] | CO2 7 | Apply an appropriate algorithm to find the shortest path from A to F. [Figure: A directed weighted graph with nodes A, B, C, D, E, F and directed edges with weights] | [7] | CO2