Skip to content

Algorithm Design and Analysis

SWE · Midterm · Spring 24

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, Spring 2024 Course Code: SE 214; Course Title: Algorithm Design and Analysis Sections & Teachers: FE (L-2, T-2: A, B & C), MHS (L-2, T-2: D) Time: 1:30 Hrs 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 generate_primes(int n) { printf("Prime numbers up to %d:\n", n); for (int num = 2; num <= n; num++) { if (is_prime(num)) printf("%d ", num); } printf("\n"); } 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 and determine the dominant factor affecting the overall time complexity. [Marks: 2, CLO1, PO2, C4] (b) void bubble_sort(int arr[], int size) { for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } How does the time complexity of the provided code changes as the input value (n) increases? Translate your answer by analyzing the number of operations performed in relation to the input size. [Marks: 3] 2. (a) Convert the array [170, 45, 75, 90, 802, 24, 2, 66] in ascending order using Radix Sort. Explain the intermediary steps, including the distribution of elements into buckets and their recombination, for each digit position during the sorting process. [Marks: 5, CLO2, PO1, C2] (b) When dealing with a dataset that is nearly sorted, with only a few elements out of place, which algorithm would exhibit better performance: Insertion Sort or selection sort? Explain your reasoning behind your choice, taking into account the characteristics and efficiency of each algorithm. [Marks: 5] (c) Compare the time complexity of Quick Sort and Merge Sort in the worst-case scenario. Which algorithm demonstrates better performance in terms of time complexity, and what factors contribute to this difference? [Marks: 5] 3. As a software developer tasked with optimizing logistics for a delivery company. Analyze to scenario and explain how you would utilize the greedy fractional knapsack algorithm to allocate packages to trucks for optimal delivery. Elaborate on the key steps involved in implementing this algorithm to maximize the total value of deliveries while ensuring that each truck does not exceed its weight capacity. [Marks: 5, CLO3, PO2, C4]