Algorithms

Daffodil International University Faculty of Science & Information Technology Department of Computer Science & Engineering Midterm Examination, Fall 2026 Course Code: CSE213, Course Title: Algorithms Level: 2 Term: 1 Batch: 70 Time: 01:30 Hrs Marks: 25 Answer ALL the 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) Explain the relationship between time complexity and space complexity. Discuss how memoization and caching can reduce execution time at the cost of additional memory, using suitable examples. (02, CO1) 1. b) Differentiate between Big-O, Big-Ω, and Big-Θ notations in terms of their asymptotic bounds. Determine the asymptotic complexity of the following function using all three notations: (03) f(n)=4n^3+7n^2+6n+12 2. a) Analyze the time and space complexity of Binary Search. Compare its average case performance with Linear Search. (02, CO2) 2. b) Analyze the time complexity of the following code snippet and express it using asymptotic notation: (1.5*2 = 03) Code Snippet 1: int main() { int n; scanf("%d", &n); int i = 1; while (i <= n) { int j = 1; while (j <= n) { printf("*"); j++; } i = i * 2; } return 0; } Code Snippet 2: #include <stdio.h> int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i *= 2) { for (int j = 1; j < i; j *= 2) { for (int k = 1; k < j; k++) { printf("Hello\n"); } } } return 0; } 3. a) Given coin denominations {2, 3, 5, 7}, design a Greedy algorithm to make change for an amount 118 . Does the greedy strategy work here! Why? (05, CO3) 3. b) A warehouse has bins, each with a capacity of 10 units. The following items must be packed into the bins: 7, 5, 6, 2, 4, 3, 8. Using the First-Fit Decreasing (FFD) algorithm: (05) • Show step-by-step how the items are assigned to bins. • Determine the total number of bins required and calculate the unused capacity in each bin. 3. c) Consider the following pseudocode for the Merge Sort algorithm: (CO3) MERGE_SORT(A, left, right) if left < right mid = (left + right) / 2 MERGE_SORT(A, left, mid) MERGE_SORT(A, mid + 1, right) MERGE(A, left, mid, right) For the array : A = [38, 12, 27, 43, 9, 31, 18, 25] • Trace the recursive calls and show how the array is divided into subarrays until each subarray contains one element. (01) • Simulate the execution of the MERGE() procedure and show the array after each merging step. (02) • Write the final sorted array after the algorithm terminates. (01) • Determine the time complexity of the algorithm in the best, average, and worst cases. (01)