Algorithm Design and Analysis

Daffodil International University Faculty of Science & Information Technology Department of Software Engineering Midterm Examination, Fall 2026 Course Code: SE214; Course Title: Algorithm Design and Analysis Sections & Teachers: AS (A, B, C), MMSI (D, E, H), MK (F, G), AAS (I, J), ABS (K), DP (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) Consider the following pseudocode for sorting an array of (n) integers in ascending order. Algorithm Sort (A, n) for i <- 1 to n - 1 do key <- A[i] j <- i - 1 while j >= 0 AND A[j] > key do A[j + 1] <- A[j] j <- j - 1 end while A[j + 1] <- key end for End Algorithm CLO-1 Level-4 i) Identify the sorting algorithm represented by the pseudocode. [Mark-1] ii) Trace the algorithm for the input array [77, 44, 55, 22, 66] by showing the states of the array after completion of each loop. [Marks-2] iii) Analyze the best-case and worst-case time complexities of the algorithm and give a brief justification for each. [Marks-2] 2. a) Suzuki and Fujimoto are two undergraduate students taking an Algorithm course in their second year of study. Both students have been asked to sort the following array in ascending alphabetical order. B | O | O | K | M | A | R | K | E | D Suzuki uses an iterative sorting technique that places one element in its correct position during each pass. Fujimoto uses a recursive sorting technique that selects the first element as a pivot and divides the remaining elements into two groups. While analyzing their algorithms, they observe that Suzuki's algorithm has quadratic time complexity in all cases, whereas Fujimoto's algorithm may have quadratic time complexity when the array is already sorted. Answer the following questions: CLO-2 Level-2 i) Classify the sorting algorithms used by Suzuki and Fujimoto. [Marks-1] ii) Visualize the steps performed by Suzuki's algorithm to sort the given array. [Marks-3] iii) Express the pseudocode for the sorting algorithm used by Fujimoto. [Marks-3] iv) Compare the two algorithms in terms of time and space complexity, and explain which algorithm is more suitable for the given situation. [Marks-3] b) A delivery company has a truck with a maximum capacity of 50 kg and wants to maximize the total profit from the goods transported. The company can take fractions of any item. The available items are listed below. Item | Weight(Kg) | Profit A | 10 | 130 B | 15 | 165 C | 12 | 120 D | 20 | 140 E | 18 | 90 F | 25 | 100 Compute the profit-to-weight ratio of each item and the optimal selection of items, including any fractions, to maximize the total profit within the truck's capacity. Describe the algorithm design strategy used in this problem. [Marks-5] 3. A file contains only colon, spaces, newlines, commas, and digits in the following frequency: colon (100), space (605), newline (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59). CLO-3 Level-4 i) Illustrate the Huffman tree and identify the Huffman code for each symbol. [Marks-3] ii) Explain why Huffman coding is used for data compression and how symbol frequencies influence code lengths. [Marks-2]