Skip to content

Algorithm Design and Analysis

SWE · Final · Fall 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 Final Examination, Fall 2024 Course Code: SE214; Course Title: Algorithm Design & Analysis Sections & Teachers: All Time: 2:00 Hrs 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) A networking company uses a compression technique to encode the message before transmitting over the network. Select an greedy algorithm to compress the size of the message and demonstrate that the size has been reduced. Suppose the message contains the following characters with their frequency: T = 9, X = 5, H = 45, C = 12, A = 13, E = 16 [Marks-5] | CLO-3 Level-4 b) You're working as a software developer, maintaining a project hosted on GitHub. During the development process, you make several changes to a document, and GitHub provides a feature to manage different versions. Version 1: "SOFTWARE" Version 2: "OFFER" Analyze the similarity between these two versions by determining the length of the longest common subsequence using dynamic programming, and also identify the subsequence. [Marks-5] c) You are a cargo manager at a shipping company. You have a cargo container with a limited weight capacity of 8 kg. Your task is to maximize the total value of the items you can load into the container without exceeding the weight capacity. Item | Weight | Value 1 | 3 | 10 2 | 4 | 10 3 | 5 | 15 4 | 2 | 9 Identify the items to load into the container that will maximize the value of the cargo using a dynamic programming approach. Remember that You cannot take a fractional part of an item ( each item is either taken whole or not taken at all.) [Marks-5] d) You are organizing a charity event where attendees can donate money using coins of different denominations. The available coin denominations are {1, 2, 4, 5} units. Predict the number of ways the attendees can donate a total of 6 units using the available coin denominations. [Marks-5] 2. You are planning a road trip across several towns. Each road between towns has a specific travel time in minutes. The road network is as follows: Home - Town A: 15 Home - Town B: 10 Town A - Town B: 5 Town A - Town C: 20 Town B - Town D: 10 Town C - Town D: 30 Town C - Town E: 15 Town D - Town E: 10 Represent the above road network as an undirected graph and answer question 2(a) & 2 (b). [Marks-5] | CLO-4 Level-5 a) Starting from "Home," you aim to explore the graph as deeply as possible along each branch before backtracking. Your chosen traversal method also follows a Last-In-First-Out (LIFO) approach. Determine the order in which the nodes are visited based on this strategy. [Marks-5] b) Explain the process of Dijkstra's Algorithm to find the shortest travel time between Home and Town E and also show the shortest path to reach Town E. [Marks-5] You are responsible for designing the network infrastructure of a new office building. The building has multiple rooms (nodes) that need to be connected via network cables (edges). Each cable has a specific cost (weight) based on the distance between the rooms. You need to connect all the rooms with the minimum total cable cost while ensuring that the network remains fully connected. A - A: cost - 6 A - C: cost - 3 C - B: cost - 10 B - D: cost - 4 D - C: cost - 2 D - B: cost - 15 E - D: cost - 1 E - C: cost - 6 Represent the above network as an undirected graph and answer question 2(c) & 2 (d). c) Draw the network tree and determine the minimum cost to connect all rooms using a strategy that starts from any room and expands the network by adding the cheapest connection to a new room. [Marks-5] d) Draw the network tree and determine the minimum cost to connect all rooms using a strategy that first sorts all the possible connections (edges) by their cost and then adds the cheapest connections while avoiding any cycles. [Marks-5]