Algorithm Design and Analysis
SWE · Midterm · Fall 24
Paper 1 of 2By SUPAN ROYSwitch
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, Fall 2024
Course Code: SE214; Course Title: Algorithm Design and Analysis
Level 2 Term 2
Sections & Teachers: FE(A, B, C), MHS(D), AAS(E), AAM(F, G), IAT(H, I)
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) void sum_of_squares_of_evens(int n) {
int sum = 0;
for (int i = 2; i <= n; i += 2) {
sum += i * i;
}
printf("Sum of squares of even num up to %d is: %d\n", n, sum);
}
How does the time complexity of the provided code change as the input value (n) increases? Translate your answer by analyzing the number of operations performed in relation to the input size. | [Marks-2] | CLO-1 Level-4
b) int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
left = mid + 1;
else right = mid - 1;
}
return -1;
}
Analyze the time complexity of this code in terms of the input size (n) and explain your reasoning. | [Marks-3] | CLO-1 Level-4
2 a) Given the array [57, 80, 42, 13, 95, 38, 29, 60], Sort this array using a divide and conquer method which is comparatively faster and time efficient. Ensure that your solution doesn't require additional memory beyond the input array itself. Visualize the step-by-step process of your chosen algorithm. Describe why you selected this algorithm for this case. | [Marks-5] | CLO-2 Level-2
b) You are managing a shop where items are stacked in a completely random order based on their weights. The items are labeled as follows: [15 kg, 3 kg, 9 kg, 7 kg, 1 kg, 12 kg].
You decide to reorganize these items from lightest to heaviest on the shelves by "repeatedly finding the minimum element and placing it at the first position on the shelves".
Explain the step-by-step process of this reorganization, and discuss the best-case and worst-case time complexity of the chosen algorithm. | [Marks-5] | CLO-2 Level-2
c) You are given the following unsorted array [12, 3, 7, 8, 4, 6, 2, 1, 18]. Convert the array in ascending order using Merge Sort. Visualize the division and merging steps clearly. | [Marks-5] | CLO-2 Level-2
3 a) You are managing a warehouse that needs to pack items into boxes for a special promotion, where each box has a maximum capacity of 75 KG. Each item has varying weight and value as follows:
Items | Laptops | Books | Plants | Jackets | Gadgets
Weight | 15 | 22 | 30 | 25 | 18
Value(USD) | 195 | 242 | 270 | 300 | 120
Identify the optimal selection of items to include in each box to maximize the total value while respecting the weight capacity constraints. Consider that you can take fractions of items if needed. | [Marks-5] | CLO-3 Level-4
"Be confident in Yourself."