Algorithm Design and Analysis Lab
SWE · Final · Spring 26
Paper 2 of 2Section 43E1Switch
Section 43E1
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
Department of Software Engineering
Faculty of Science & Information Technology
Lab Assessment, Spring 2026
Final
Course Code: SE215; Course Title: Algorithm Design & Analysis Lab
Sections & Teachers: 43E1 (AF)
Time: 40 Minutes
Marks: 25
Question 1: You are given n items, each with weight and value. Also given a knapsack with capacity W. Write a program using Dynamic Programming to determine the maximum total value that can be obtained without exceeding the capacity.
Input:
- First line: Integer n (number of items)
- Second line: n integers (weights)
- Third line: n integers (values)
- Fourth line: Integer W (capacity)
Output:
- Maximum achievable value
Sample Input | Sample Output
4 | Maximum value = 7
2 3 4 5 |
3 4 5 6 |
5 |
Question 2: You are given n items, each with weight and value, and a knapsack with capacity W. You must solve the Fractional Knapsack problem using a greedy approach.
Special Condition:
- Take the last two digits of your student ID
- If their sum is even -> use Insertion Sort
- If their sum is odd -> use Selection Sort to sort items based on value/weight ratio (descending) before applying greedy selection.
- Show the calculation in the word file
Input:
- First line: Integer n
- Second line: n weights
- Third line: n values
- Fourth line: Capacity W
Output:
- Maximum obtainable value (fraction allowed)
Requirements:
- Must implement the specified sorting algorithm manually
Sample Input | Sample Output
3 | Maximum value = 240.00
10 20 30 |
60 100 120 |
50 |