Algorithms
CSE · Final · Spring 26
Paper 2 of 2Batch 68 · Nahid Ahasan KhanSwitch
Batch 68
Paper 2 of 2
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, Spring 2026
Course Code: CSE 213, Course Title: Algorithms
Level: 2 Term: 1 Batch: 68
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. Explain the concept of the Longest Decreasing Subsequence (LDS).
Given the sequence : 9, 4, 7, 6, 1, 3, 2, 5, 1
CO1
a) Identify valid longest decreasing subsequence from the above given sequence
03
b) Briefly explain how it differs from the Longest Increasing Subsequence (LIS)
02
2. a) Consider the following operations on a set of elements {1,2,3,4,5,6}:
• Union(1,2)
• Union(2,3)
• Union(4,5)
• Find(3)
• Union(3,5)
• Find(5)
Apply an appropriate algorithm's pseudocode to visualize the following operations:
• The parent array after each union
• The result of each Find operation
05
CO2
3. a) For the given two strings below construct the DP Table to find the LCS length.
Also show the LCS string.
"ABCBDABBD" & "BDCABABDBB"
05
CO3
b) Given coin denominations {2, 3, 5, 7}, construct a DP table to find the
minimum no of coins required for 9 tk. Show the required coin values.
05
c) While traveling through the hills of Bangladesh, Arif found a few valuable items. His backpack had limited capacity, so he had to choose wisely. He could either take an item completely or leave it—no splitting allowed. To maximize the total value, Arif carefully selected the best combination of items without exceeding the weight limit. If his backpack can hold 9 kg, what will be his maximum profit? Construct a detailed table.
05
Golden Statue | Ancient Book | Rare Spices | Silver Coins
weight(kg) | 2 | 3 | 4 | 5
Price(per unit) | 300 | 550 | 550 | 700
d) Construct strongly connected components for the following graph. Show the detailed steps:
[Figure: A directed graph with vertices A, B, C, D, E, F, G, H, I, J, K and directed edges between them.]
05
CO3
e) Construct Topological Sorting order for the following graph. Show detailed steps:
[Figure: A directed acyclic graph with vertices labeled 0, 1, 2, 3, 4, 5, 6, 7 and directed edges connecting them.]
05
f) Construct the shortest path for the following figure where the starting vertex is 'A'. Show detailed steps:
[Figure: A weighted undirected graph with vertices A, B, C, D, E, F and weighted edges between them.]
05