Algorithm Design and Analysis
SWE · Midterm · Spring 24
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]