Design & Analysis of Algorithms — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

4. Parts of a question must be answered together. 5. Write all the intermediate steps, wherever required to get full credits. Q1. (a) List all the topological orderings of the Directed Acyclic Graph (DAG) G given below. (b) Consider the following procedure SUM-ARRAY which computes the sum of n numbers in array A[I:n]. SUM-ARRAY (A, n) 3 sum = sum + All] 4 return sum State a loop invariant for this procedure, and use its initialization, maintenance, and termination properties to show that the SUM-ARRAY procedure returns the sum of the numbers in All-ml. 3 (c) Quicksort partitions an array into two subarrays based on a pivot element. The running time depends on how balanced the partition is. Suppose at each step, the pivot divides the array into two parts in the ratio 1:3. Formulate the recurrence relation for the running time of Quicksort in this case. Solve the recurrence and determine the time complexity. 3 (d) Consider a hash table of size 11 with the hash function h(k) = k mod 11. Insert the keys 21, 32, 43, 54, 65, and 76 into the table. Handle any collisions using linear probing. 3 (e) A matrix multiplication technique reduces the number of recursive multiplications by dividing matrices into submatrices and combining results using fewer multiplications than the conventional method. Identify the algrim and comput the product he following matics using the same Given two matrices: (f) Consider the interval scheduling problem wherein we are given a resource 4 and set of requests each having a start time and finish time. The goal is to maximize the number of requests scheduled. Show that the greedy strategy of selecting the request with the fewest incompatible requests does not always yield an optimal solution for this problem. (g) Let Sc V be a subset of vertices in a connected, weighted, undirected graph, and let V-S denote the remaining vertices. Suppose an edge (u,v) has the minimum weight among all edges connecting S and V-S. Determine whether this edge should be included in a Minimum Spanning Tree (MST). 5 Justify your answer. (h) A delivery company has packages with weights {2, 5, 7, 3, 9} and truck capacity 15 kg. Design a greedy algorithm to maximize the number of 5 packages loaded. Explain its time complexity. Q2. (a) Which sorting technique is most efficient if the range of input data is not significantly greater than the number of elements to be sorted and runs in @(ntk) time, where n is the size of the array and k is the range of the non-negative key values. Sort the array A= {5, 9, 0, 1, 5, 4, 2, 0, 6, 9} using the 7 same algorithm. (b) Consider the following two algorithms used for sorting a list of numbers: Algorithm A preserves the relative order of equal elements and follows a divide-and-conquer approach, using extra memory. Algorithm B uses a tree-based structure, requires minimal extra space, but does not preserve relative order. i. Identify Algorithm A and Algorithm B.