Skip to content

Algorithm

CIS · Final · Spring 26

Batch 22

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 Faculty of Science & Information Technology Department of Computing and Information System Final Examination, Spring-2026 Course Code: CIS132, Course Title: Algorithms Level: 1 Term: 3 Exam Duration: 2 Hours Marks: 40 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) Define the concept of an algorithm and classify the various types of algorithms with relevant examples. [3] b) Analyze the given code to find out the time complexity. [3] int cube(int n) { int count = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) count += 1; return count; } c) Given the recurrence relation, T(n) = 2T(n/2) + n Solve it using an appropriate method and determine its asymptotic time complexity. [4] 2. During a flood, a relief-camp receives 9 trucks carrying different types of items and people. Each item is assigned a priority weight (1 = highest priority, 9 = lowest priority) based on urgency. Item | Priority (Weight) Medicine boxes | 1 Bottled water | 2 Food packets | 3 Life jackets | 4 Rescue Team | 5 Reconstruction Members | 6 Fund Team | 7 Journalists | 8 Member of Parliament | 9 However, the trucks arrive in a random (unsorted) order: Bottled water -> Member of Parliament -> Food packets -> Journalists -> Life jackets -> Rescue Team -> Medicine boxes -> Fund Team -> Reconstruction Members a) Apply Insertion Sort and Quick Sort to organize the given relief items according to priority. Show major steps of execution. [8] b) Analyze the number of comparisons and swaps required in Quick Sort and Insertion Sort for this dataset. [2] 3. [Figure: A graph with 9 vertices labeled 0 to 8, with weighted edges connecting them] a) Perform Depth-First Search (DFS) starting from node 0 and write the traversal order. [3] b) Apply Prim's Algorithm (starting from node 0) to construct the Minimum Spanning Tree (MST). Show the selected edges step by step. [3] c) Apply Kruskal's Algorithm to construct the MST. Show edge sorting and selection process. [3] d) Compare the results of Prim's and Kruskal's algorithms. Are the MSTs the same? Justify your answer briefly. [1] 4. a) You have an unlimited supply of 2-taka, 3-taka, 4-taka, and 6-taka notes. Using the dynamic programming approach, determine the minimum number of notes required to make a total of 15 taka. Show the necessary steps of your solution. [5] b) A gym worker is organizing weights by stacking them on shelves. The weights (in kilograms) are given below: 12, 16, 18, 8, 16, 12, 10, 4, 6, 10, 12, 16, 20, 10, 24 Each shelf has a load capacity of 40 kg. Using the Bin Packing algorithm concepts, solve the following: i. Determine the Lower Bound (LB) for the minimum number of shelves required. ii. Apply the First-Fit (FF) algorithm to pack the weights and show the arrangement of items in each shelf. iii. Apply the First-Fit Decreasing (FFD) algorithm and show the final arrangement after sorting. iv. Find the optimal bin packing solution (minimum possible number of shelves) and compare it with FF and FFD results.