Skip to content

Algorithms

CSE · Final · Fall 24

Batch 65

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 Computer Science and Engineering Final Examination, Fall -2024 Course Code: CSE213, Course Title: Algorithms Level: 2 Term: 1 Batch: 65 Time: 2.0 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) You are given a sequence of numbers. Apply an appropriate technique to find the length of the Longest Increasing Subsequence (LIS) for the given elements. Elements: [0, 9, 2, 5, 3, 7, 11, 8, 10, 13, 6] | [5] | [CO2] b) A directed graph is given below. Apply Topological Ordering approach on the given graph and find the order of the vertices for the graph (Show all the necessary steps). | [5] [Figure: A directed graph with nodes A, B, C, D, E where A points to B and C, C points to D and E, D points to E] 2. a) Hasan is given an undirected graph. Prepare a minimum spanning tree from the graph where the proposed algorithm works through the edges of the given graph. | [5] | [CO2] [Figure: An undirected graph with nodes A, B, C, D, E, F and weighted edges: A-F(7), A-C(3), A-B(10), B-C(5), B-E(4), C-D(6), C-F(8), C-D(3), D-E(2), C-E(2)] b) You are given an undirected graph below. Show the visited sequence to find node F in the graph. Choose the appropriate technique where the STACK data structure is applied. Starting Node: A | [5] [Figure: An undirected graph starting at A, connected to C, B, D, E, F in a path/cycle layout] 3. a) You are given 4 products, each with a weight and a value. You also have a bag that can carry up to 6 units of weight. Your goal is to obtain the maximum value of the items you can place in the bag without exceeding the weight limit. Also you are not allowed to choose a partial weight of the products. Apply an appropriate approach to make a maximum profit. | [8] | [CO3] Product No. | Weight | Value 1 | 2 | 20 2 | 3 | 15 3 | 4 | 24 4 | 5 | 30 b) Determine the appropriate algorithm for 3. (a) and analyze its time complexity. | [2] 4. a) Steve Mark loves to visit places. He decided to visit some places by applying the cost-minimizing formula. The following graph represents four places by indicating four nodes. There are some distances in km from one node to another. Estimate the shortest path from the source to the remaining nodes by applying a suitable algorithm. | [8] | [CO3] [Figure: A directed graph with nodes Source, A, B, C, D with weighted edges: Source-A(10), Source-C(-2), A-B(3), B-D(4), C-D(15)] b) Analyze the performance of the Bellman-Ford algorithm in the presence of negative cycles. | [2]