Algorithms
CSE · Final · Summer 26
Section 69-K · Batch 252
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 2026
Course Code: CSE 213, Course Title: Algorithms
Level: 2 Term: 1 Batch: 69
Time: 02:00 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. Given the sequence : 4, 4, 6, 4, 1, 3, 2, 2, 1
1. a) Identify valid longest non decreasing subsequence (LNDS) from the above given sequence | 03 | CO1
1. b) Briefly explain how it differs from the Longest Decreasing Subsequence (LDS) | 02 |
2. Consider the following two strings:
- X = ABCBDAB
- Y = BDCABA
Apply the LCS (Longest Common Subsequence) algorithm to find the LCS of the two strings. Use the appropriate algorithm's pseudocode to show:
- The LCS table after each character comparison
- The final LCS length
- The resulting LCS sequence | 05 | CO2
3. a) Given coin denominations {3, 5, 2, 7}, construct a DP table to find the minimum number of coins required for 9 taka. Show the required coin values. | 05 | CO3
3. b) During a flood relief operation in Bangladesh, Nabil prepares a backpack to deliver essential supplies to affected families. His backpack can carry a maximum weight of 10 kg. Each available item has a specific weight and value (importance). Nabil can either take an item completely or leave it behind, but he cannot take a fraction of any item.
Rice Pack | Medicine Box | First Aid Kit | Baby Food Pack
weight (kg) | 4 | 3 | 4 | 5
Price (per unit) | 300 | 550 | 400 | 700
What is the maximum total value of supplies Nabil can carry? Construct a detailed table using the 0/1 Knapsack Dynamic Programming algorithm and identify the selected items. | 05 |
3. c) During a trip to the hilly areas of Bangladesh, a group of students wants to connect several villages with minimum-cost roads. The following graph shows the possible roads and their construction costs. Apply Prim's Algorithm to construct the Minimum Spanning Tree (MST), Starting from vertex A.
[Figure: A weighted undirected graph with vertices A, B, C, D, E, F, G and various edge weights] | 05 | CO3
3. d) Construct strongly connected components for the following graph. Show the detailed steps:
[Figure: A directed graph with 6 vertices numbered 1 to 6 and directed edges connecting them] | 05 |
3. e) Construct Topological Sorting order for the following graph. Show detailed steps:
[Figure: A directed acyclic graph with vertices 0, 1, 2, 3, 4, 5 and directed edges] | 05 |
3. f) Construct the shortest path for the following figure where the starting vertex is 'A'. Show detailed steps:
[Figure: A weighted directed graph with vertices A, B, C, D, E, F, G and edge weights] | 05 |