Shabjalal University of Science and Technology Department of Computer Science and Engineering and year Ist Semester Final Examination-2021 Session— 2019-20 Course No.— CSE237 Course Title— Algorithm Design & Analysis Time— 3 Hours Credit: 3.00 Total Marks# 100 (Answer all the questions and keep your answers to the point.) Group A GQ Answer the following Questions (Any Five ) 2* 5-10 a) Ifa problem does not have overlapping sub-problems, what would happen if Dynamic Programming is used to solve the problem? b) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memoization, Is it true? Justify your answer. ) Can we say the runtime of an algorithm is 0 (2%) when the actual runtime is roughly (i) 2 +¢, (i) 2% +c. 4) What are the four basic properties to be a good hash function? e) Build LCP array for the string "aacaabaac", ) Which data structure is suitable to implement a Priority Queue? What are the complexities of push(x), pop0, and top() operations, 8) Write the names of two sorting algorithms that apply the Divide and Conquer approach. Write their time complexities in Best, Average, and Worst case scenarios. h) Draw a graph with negative edges where Dijkstra will be able to find the shortest path between any pair of nodes. Q2 Answer the following Questions (Any Four ) 5 x 4-20 a) Check if the following statement is True or False, If the statement is False, write the correct statement, 1) Krushkal is better than Prims for finding the Minimum Spanning Tree within a graph in terms of time-complexity. 2) The insertion complexity of an element in a Heap data structure is 0 (NlogN), where N is the number of elements currently on the heap. 3) Bellman-Ford will be able to find the shortest path between 2 nodes of a weighted-connected graph if all the edges are positive weighted, 4) Memory complexity of the Matrix-Chain-Multiplication algorithm is 0 (N*) 5) Sometimes Bottom-up approach of dynamic programming can be more memory- efficient compared to the Top-down approach. ) b) Assume there is only one classroom and you have to schedule the following classes, ‘The duration of each class is 1 hour and your objective is is to maximize the totalnumber of students served, © Classes start from 11:00 am in the morning. © Each of the classes must end before their respective deadline. © Classes can be arranged in any arbitrary order. It is okay to start CSE333. anytime from 11:00 am to 1:00 pm, as long as it ends before 2:00 pm, Class Cade] ‘Students CSEISS 130 CSE233 6 CSE127 100 CSE237 110 CSE333 120 ©) What does Big-0 and Big-@ signifies in an algorithm? Write the pseudocode of an algorithm where the Big-O and Big-® are 2 different functions. 4) Given a polygon represented by the points A(2,2), B(4,2), (4,4) what would be the updated co-ordinates of the points 4,8, if you rotate the polygon 90 degrees counter clockwise with respect to the origin (0,0). ©) Apply Merge-sort algorithm to sort the following array. arr{] = {12, 3, 4, 13, 8, 9, 10, 5} Just show the states as the arrays divide and merge at each step. You don't have to indicate how it is happening. 9 Apply Extended Euclid algorithm on the pair of numbers 50 and 30 to find ged(s0, 30), x, and y such that 50x + 30y = ged(50, 30) Answer the following Questions (Any Two). 102-20 a) Check if the following graph has an Euler path. If there is, use Fleury’s algorithm to find the Euler’s path, Show each steps. ©) Check if the pattern aacaac exists in the text aacaabaacaac using KMP algorithm, Show each steps. ©) Answer the following questions. 1. Write a function to check if the line segment between a pair of points AC«ty1) and B(x2,y2) intersects with the line segment between the pair of points C(x, ys) and D(xs, y4). struct point{ int x, y; point(int _x, int _y) fx =_x, y = _yJ } bool do_segments.intersect(point A, point B, point C, point D) { eeYOUR CODE HERE .. // YOU ARE FREE TO USE ANY PROGRAMMING LANGUAGE .... // EVEN PSUDOCODE IS ACCEPTABLE. 2, Use the Graham Scan approach to find the Convex Hull of the given points. show each steps graphically, You don’t have to do the calculations to check anticlockwise orientation at each step. (10,10), (27, 5), (15, 5), (23, 0), (35, 5), (30, 10), (20, 20) Group B Q4 Answer the following Questions (Any Five ) 2* 5010 a) Give example of an NP-hard problem, (don’t just write the name of the problem. Write the objective briefly and clearly.) b) How can we solve the Maximum Bipartite Matching using the Ford Fulkerson Algorithm? ©) What is the time complexity of checking if a word exists in a dictionary if every word of the dictionary has been inserted in a Trie data structure? 4) Draw a graph where BFS will work faster than DFS to reach a node from a root node. Your example graph should be unweighted, It can be either directed or undirected. ©) Apply Euclid Algorithm to find the GCD of the pair of numbers 35 and 60, £) "Dijkstra qualifies as a greedy algorithm”, why? g) Define Loop Invariant. h) What are the Bridges and Articulation Points in a connected graph? Q5 Answer the following Questions (Any Four ) 5 x 4=20 a) Apply Sieve of Eratosthenes to find all the prime numbers up to 20 b) Calculate the Longest Increasing Sub-sequence of the following array. You can use either Top-down or Bottom-up approaches. Show each steps/table. arr[] = {3, 4, 13, 8, 9} ©) Find a valid topological sorting order for the following graph, a --> b indicates that a must appear BEFORE b in a valid order. 4) Calculate the Hash value of the word aacaabacb with the mapping 1 a2—>b 3 Use the prime 17 as the base and mod the values at each step with 107,©) Use the Krushkel algorithm to find the Minimum Spanning Tree of the following weighted-connected graph, ) Build a Sparse Table for performing Range Minimum Query with the following values. The array is 0-indexed, arr{] = (12, 3, 4, 13, 8, 9, 10, 5} Then, find the minimum value within the range (2 to 7). 6 Answer the following Questions (Any Two). 10x2=20 ) Apply Ford Fulkerson algorithm to find the Maximum Flow permitted by the following network, Source node is 1 and the sink node is 6. 5) Find all the strongly Connected Components in the following directed graph using an algorithm of your preference. Time complexity should not exceed O(N). ©) Consider the shapes following matrices: [2x4], [4xé], [6x40], [40x8] 1, Find the minimum number of scaler multiplication required to find the Matrix Multiplication result, 2. What is the optimum order of that multiplication? Show using brackets. Further explanation is unnecessary,