Skip to content

Algorithm Design and Analysis

SWE · Midterm · Fall 24

Paper 1 of 2By SUPAN ROYSwitch

Paper 1 of 2

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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."