Algorithm Design and Analysis
SWE · Midterm · Spring 25
Paper 1 of 2By Shafiur Rahman Shafim (242)Switch
Paper 1 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
Midterm Examination, Spring 2025
Course Code: SE214; Course Title: Algorithm Design and Analysis
Sections & Teachers: FE(A,B,C,N), MRN(D,M), IS(E,F), CP(G,H), NJN(I,J), MMSI(K,L)
Time: 1 Hour 30 Mins
Marks: 25
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) #include <stdio.h>
int find_missing(int arr[], int n) {
int sum = n * (n + 1) / 2;
for (int i = 0; i < n - 1; i++)
sum -= arr[i];
return sum;
}
int main() {
int arr[] = {1, 2, 4, 5, 6};
printf("%d\n", find_missing(arr, 6));
return 0;
}
Analyze the time complexity of given code by calculating the operations it will require. [Marks-2] [CLO-1 Level-4]
b) Explain under what conditions would you prefer Binary Search over Linear Search algorithm. [Marks-3]
2. a) You work as a university librarian, and students frequently borrow and return books. As a librarian, you need to organize returned books, which are currently in random order as follows:
[305, 120, 275, 110, 190, 260]
To sort them before shelving, you start with the second book, placing it in the correct position among the sorted ones. You repeat this for each book until all are in ascending order.
Explain the step-by-step process of sorting the books and discuss the best-case and worst-case time complexity of the chosen algorithm. [Marks-5] [CLO-2 Level-2]
b) You need to organize a list of exam scores for analysis quickly. The scores are:
[45, 78, 32, 10, 88, 39, 25, 55]
Using a divide-and-conquer approach, you select a reference point (pivot) and rearrange the scores so that smaller values come before it and larger values after it. You repeat this process for each section until the list is sorted.
Visualize the step-by-step process of your chosen algorithm. Describe why you have selected this algorithm for this case. [Marks-5]
c) You are given the following unsorted array:
[15, 5, 9, 11, 6, 8, 3, 2, 20]
Convert the array into descending order using Merge Sort. Visualize the division and merging steps clearly. [Marks-5]
3. A courier company is tasked with carrying goods for a trip, but the weight limit is 50 kg for each trip. The company can take fractions of items, which means it can take parts of an item if the whole item doesn't fit. Each item has a specific weight and value. [Marks-5] [CLO-3 Level-4]
You are given the following information about the items:
Item | Printer | Tablet | Laptop | Camera | Monitor
Weight (kg) | 15 | 10 | 20 | 18 | 25
Value ($) | 90 | 60 | 100 | 75 | 120
Using the Fractional Knapsack Algorithm, Identify the items and total value to be selected to maximize the total value while staying within the weight limit of the truck. Consider that you can take fractions of items if needed.