Advanced Algorithms — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

B.Sc. (H) Computer Science (CBCS) g) •h) Write the recurrence relation for the divide and conquer algorithm for the Segmented Least Squares problem. Differentiate between maximum.matching and perfect matching. i) Explain the structure of a Fibonacci heap. j) k) Given the following key-value pairs, insert them into a dictionary and show the structure: Differentiate between a standard trie and a compressed trie. Construct an optimal Huflinan code for the characters A, 8, C, D, E, given the following set of frequencies: For the following splay tree: Delete 15 using the splay-tree deletion algorithm. Show the intermediate splay trees after splaying and merging steps. Consider the elements { 1, 2, 3, 4, 5, 6}. Each of the elements are in thei.r singleton disjoint-sets. Perfom the following operations and show the resulting sets after each operation. Show the Red Black tree which results after inserting the following ke: sequence into an initially empty tree: 40, 32, 22, 10, 17. Find the minimum sparming tree for the following graph using kruskal algorithin. 4.a) Compute the shortest path from node 'S' to node "T' using Dijkstra's algorithm. 5 b) Does Dijkstra's algorithm work with a graph having negative edge weights? 5 Justify your answer using appropriate arguments or example. 5.a) Consider the following set of intervals { in, i2, .., in), with start time si and finish 5 time fi. Determine the largest set of mutually compatible intervals. .... Interval i Start time si Finish time fi 6.a) b) Generate an example of an array of size 5 with at least 7 inversions. Just] example constructed. What is the maximum possible number of inversio] can occur in the array of size 5? Prove the following statement: Let fbe any s-t. flow, and (A, a) any s-t cut. Find the maximum flow, from node S to node T, for the following graph.12A,82016T Also, identify the cut conesponding to the flow. Consider the following set of 8 points in a 2D plane: Apply the Divide-and-Conquer Closest Pair Algorithm to this input and compute the minimum distance. Construct subsets decision tree that shows all the subsets of the set {6,2,4}.