Skip to content

Algorithms

CSE · Final · Fall 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 Department of Computer Science and Engineering Faculty of Science & Information Technology Final Examination, Fall 2022 Course Code: CSE214 Course Title: Algorithm Level: 2 Term: 1 Batch: 58, 59, Old Syllabus Time: 2 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) Consider the following algorithm and the given array. Now run the algorithm on the array and demonstrate how the array will be updated at each iteration. Construct every single step. [6] CO1 A[5] = {4, 7, 2, 6, 8, 3, 1, 5}; for(j=0; j<8; j++){ min = a[j]; position = j; for(i=j+1; i<n; i++) { if(min>a[i]) { min = a[i]; position = i; } } temp = a[j]; a[j] = a[position]; a[position] = temp; } b) Analyze the Big-Oh(O) complexity of the above code snippet. [2] 2. You are given with the Adjacency Matrix of 3 graphs as follows. Now for each of the following graphs you need to categorize if the graph is: (i) Directed? (ii) Weighted? (iii) Connected? (iv) Tree? [8] CO2 a) [Figure: Adjacency matrix for graph a, 4x4 matrix with values 0 2 7 0, 2 0 0 3, 7 0 0 5, 0 3 5 0] b) [Figure: Adjacency matrix for graph b, 4x4 matrix with values 0 1 0 0, 0 0 1 1, 0 0 0 0, 0 0 0 0] c) [Figure: Adjacency matrix for graph c, 4x4 matrix with values 1 1 0 0, 0 0 0 0, 0 0 0 1, 0 0 0 1] 3. a) Build the tree for the call fibonacci(5) using both dynamic programming and divide and conquer approach. [4] CO3 b) Suppose you have written the word spire while composing a document in a word processor. The spell checker has reported it as an invalid word and suggested the following replacement words: 1) expire 2) sapphire Your first task is to construct the Longest Common Subsequence of the two replacement words with spire. In other word you have to construct 2 LCS values: 1) spire, expire 2) spire, sapphire [6] c) Now based on the LCS values, you have to choose which one of the two replacement words is more likely to be the correct word? [2] 4. a) Absent-minded Makhon has a problem when getting ready to go to work in the morning. He sometimes dresses out of order. For example, he might put his shoes on before putting the socks on, so he'll have to take the shoes off, put the socks on and then the shoes back on. There's also a shirt, tie, belt, shorts, pants, watch and jacket that have to be put on in a certain order. The order between different parts of clothing forms a graph. Shirt before tie means there's an edge from shirt to tie. Now help Makhon to find a complete order of clothing and getting ready for office. Construct the complete order. [7] CO4 [Figure: Directed graph with nodes socks, shorts, shoes, pants, belt, shirt, jacket, tie, and watch with various directed edges] b) What is the name of your algorithm in 4.a)? [1] c) Consider the following graph. Here each vertex denotes an airport and each edge denotes the duration of a flight between two consecutive airports. You have to determine the fastest route from airport 1 to 5. i. Identify the problem you are going to solve. ii. Select appropriate algorithm for solving this problem. [4] [Figure: Weighted graph with nodes 1, 2, 3, 4, 5, 6 and directed/undirected edges with weights between them]