Algorithm Design and Analysis
SWE · Final · 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
Final Examination, Spring 2024
Course Code: SE 214; Course Title: Algorithm Design and Analysis
Sections & Teachers: FE (A, B, C), MHS (D)
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) Analyze the concepts of independent subproblems and overlapping subproblems within the realm of dynamic programming. Compare and contrast how the Divide and Conquer strategy addresses these aspects. Provide examples to illustrate the differences in approach and discuss the implications of each strategy on problem-solving efficiency and algorithmic complexity. | 5 | CO3, PO2, C4
b) You're going on a hiking trip and can only carry a limited weight in your backpack. You have a list of items, each with its weight and value. How would you use the 0/1 knapsack problem to determine the optimal selection of items to maximize the total value you can carry without exceeding the weight limit? | 5
c) You are designing a file compression software similar to ZIP or RAR. Explain how you would implement Huffman coding to compress text files efficiently. Provide an example of how variable length Huffman coding would be applied to compress a sample line of text. | 5
d) You're developing software for a genetics research institute. The institute is studying DNA sequences of two organisms. Consider the DNA sequences:
Organism A: "AGGTAB"
Organism B: "GXTXAYB"
Your task is determining the length of the longest common subsequence between these DNA sequences using dynamic programming. | 5
2. a) Define what it means for a graph to be connected. Provide examples of connected and disconnected graphs, and explain how connectivity impacts various graph algorithms. | 5 | CO4, PO3, C5
b) Consider an unweighted graph with vertices A, B, C, D, and E, where the edges are: AB, AC, BC, BD, and CE. If you're starting from vertex A, apply BFS to find the shortest paths to all other vertices. Evaluate the performance of BFS from the context of time complexity. | 5
c) You have a large social network represented as a graph, where nodes represent people, and edges represent connections (friendships). You want to find all friends from a given person. Describe how you would employ DFS to traverse the graph and find the desired connections. Evaluate the time complexity of DFS in this context, considering the size of the network and its structure. | 5
d) You're working on a logistics management system for a delivery company that operates in a city with a complex road network. The company wants to optimize its delivery routes to minimize travel time between various locations.
Locations (Nodes): A, B, C, D, E, F
Roads (Edges) with Travel Times (in minutes):
A - B: Time - 5
A - C: Time - 3
B - D: Time - 6
C - D: Time - 4
C - E: Time - 2
D - E: Time - 7
D - F: Time - 5
E - F: Time - 3
Apply Dijkstra's Algorithm to find the shortest travel time between Location A and Location F. | 5
Note: Provide detailed explanations and examples to support your answers. Marks will be awarded for clarity, accuracy, and understanding of the concepts.