Back to Other Questions [Of this Course]
👁️ 128 views
University of Barishal Logo

University of Barishal

Department of Computer Science and Engineering

Final Exam

Course Title: Design and Analysis of Algorithms (CSE-2201)

Semester: 4th | Session: 21-22

Time: 180 minutes | Marks: 60.00

Course Teacher: Md. Erfan

Exam Date: July 16, 2025

View 27 Topic-wise Questions for this Course

(Answer any FIVE questions)

1.

a) Illustrate the operation of merge sort on the array A<41, 52, 26, 38, 57, 9, 49 >. Explain Worst case, Best case, and Average Case complexity of Insertion sort.

Please SUBSCRIBE to view full question

Topics: Merge Sort , Space Complexity , Time Complexity Solution is Coming!
3 Marks
b) Use Strassen's algorithm to compute the matrix product below. Show your work.

Please SUBSCRIBE to view full question

Topics: Strassen's Algorithm Solution is Coming!
3 Marks
c) Given the following points: Perform Graham Scan step by step and list the final convex hull vertices in order.

Please SUBSCRIBE to view full question

Topics: Graham Scan Solution is Coming!
6 Marks
2.

a) Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.

Please SUBSCRIBE to view full question

Topics: Priority Queue , Queue , Stack Solution is Coming!
6 Marks
b) Find Longest Common Subsequence using Dynamic Programming Technique with illustration X={A, B, C, B,D, A,B) and Y={B,D,C,A,B,A}.

Please SUBSCRIBE to view full question

Topics: Dynamic Programming (DP) , Longest Common Subsequence (LCS) Solution is Coming!
6 Marks
3.

a) Consider a hash table of size 7 with hash function h(k) = k mod 7. Draw the table that results after inserting in the given order, the values, 15, 25, 12, 43, 17, 21, 79 for each of the scenarios below: i) When collisions are handled by separate chaining. ii) When collisions are handled by linear probing. iii) When collisions are handled by double hashing. Using a second hash function h'(k)=5-(k mod 5).

Please SUBSCRIBE to view full question

Topics: Hash Table Solution is Coming!
6 Marks
b) Define a Linked List. Write a function to insert an element in the middle of a Linked List. Let consider the following linked list with 12 as the head. Now write an algorithm to insert a new node (15) in the middle of node 18 and 7.

Please SUBSCRIBE to view full question

Topics: Linked List Solution is Coming!
6 Marks
4.

a) Write down the number of hits does the following string matching algorithms encounter in the text T=abahababaaba when looking for the pattern P=ababa using Finite state automata algorithm.

Please SUBSCRIBE to view full question

Topics: Finite State Automata , String Matching Algorithm Solution is Coming!
5 Marks
b) Define divide and conquer. Write down the pseudo code for finding the result of 7^54 % 8. using divide and conquer.

Please SUBSCRIBE to view full question

Topics: Divide and Conquer Solution is Coming!
4 Marks
c) Represent the tower of hanoi problem using master theorem of recurrence.

Please SUBSCRIBE to view full question

Topics: Tower of Hanoi Solution is Coming!
3 Marks
5.

a) Topological sort algorithm for Directed Acyclic Graph (DAG) is a linear arrangement of vertices such that for every directed edge x-y, vertex x comes before y in the arrangement. Topological sorting is only applicable on graphs that are DAG. Now your task is to prove that from the above graph that, "There can exist more than one topological sorting for a given graph." Using i. DFS ii. Kahn's Algorithm

Please SUBSCRIBE to view full question

Topics: Depth-First Search (DFS) , Kahn's Algorithm , Topological Sorting Solution is Coming!
6 Marks
b) Define disjoint set and answer the following questions. i. Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. ii. During the execution of CONNECTED-COMPONENTS on an undirected graph G(V,E) with k connected components, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of IVI, |E|, and k.

Please SUBSCRIBE to view full question

Topics: Disjoint Set , Graph Theory Solution is Coming!
6 Marks
6.

a) Consider the following adjacent list for directed graph. adj(y)= [x], adj(x) = [z], adj(z) = [y,w], adj(w)= [x], adj(s) = [z,w], adj(v) = [s,w], adj(t)=(u,v), adj(u) = [v]. i. Draw a graph from the above information. ii. Rewrite the procedure DFS, using a stack to eliminate recursion. iii. Identify the tree edge, back edge, cross edge and forward edge for the graph.

Please SUBSCRIBE to view full question

Topics: Depth-First Search (DFS) , Graph Edge Classification , Graph Representation Solution is Coming!
6 Marks
b) Define Relaxation. Run the Bellman-Ford algorithm on the directed graph of the figure, using vertex "s" as the source. In each pass, relax edges in the same order as in the figure, and show the d and fl values after each pass. Now, change the weight of edge .(z,x) to 4 and run the algorithm again, using s as the source.

Please SUBSCRIBE to view full question

Topics: Bellman-Ford Algorithm , Graph Algorithms , Relaxation Solution is Coming!
6 Marks
7.

a) Consider the foiling weighted and undirected graph to find the path from A to every other vertexs using Dijkstra's algorithm.

Please SUBSCRIBE to view full question

Topics: Dijkstra's Algorithm , Graph Algorithms Solution is Coming!
4 Marks
b) What do you mean by flow network and residual network? Use the Ford-Fulkerson Algorithm to find a flow function that maximizes the flow in the below network having the capacities shown and calculate the total flow that results. List the augmenting paths that you use to get your solution in order to get full credit.

Please SUBSCRIBE to view full question

Topics: Ford-Fulkerson Algorithm , Graph Algorithms Solution is Coming!
4 Marks
c) Define bipartite graph. Write down the algorithm of Edmonds-Karp and when we use the algorithm with appropriate example.

Please SUBSCRIBE to view full question

Topics: Bipartite Graph , Edmond-Karp's Algorithm Solution is Coming!
4 Marks
8.

a) Consider the given weighted graph. i. Run Prim's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree. ii. Run Kruskal's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree.

Please SUBSCRIBE to view full question

Topics: Graph Algorithms , Kruskal's Algorithm , Minimum Spanning Tree (MST) , Prim's Algorithm Solution is Coming!
6 Marks
b) Run the following All-Pair-Shortest-Paths algorithms on the weighted and directed graph. i. EXTEND-SHORTEST-PATHS algorithm ii. Floyd-Warshall algorithm

Please SUBSCRIBE to view full question

Topics: All-Pair-Shortest-Paths Algorithm , Floyd-Warshall Algorithm , Graph Algorithms Solution is Coming!
6 Marks
View 27 Topic-wise Questions for this Course

Contributors of this Question:

Role Name Date
Prepared By (Teacher): Md. Erfan July 16, 2025
Uploaded By: Margia Rowshon July 16, 2025, 2:25 p.m.
Reviewed By: N/A N/A
Back to Other Questions [Of this Course]