Algorithms
CSE · Final · Fall 22
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]