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

(c) Give the DFS traversal sequence from vertex 0 for the following graph : (4) Name of th? Paper : Design And Analysis of Name of `the Course : Generic Elective GE 2. The Paper has two sections. 1. (a) Given keys (26, 30, 42, 35, 50) and table size = 7, insert the keys using hash function h(k) = k mod 7 and resolve collisions using linear probing. (b) Find the total number of comparisons made by the insertion sort algorithm for the following array A: (c) Can a greedy algorithm always give the optimal solution for all optimization problems? Justify your answer with an example. (3) (d) (i) What is the time complexity of the Heap Sort algorithm? (i) How many comparisons does the Heap Sort algorithm make in order to sort an already sorted array? (3) func(n - 1, source, dest, aux); cout << "Move disk" << n << " from " << source if(n <= 1) return; func(n/3); • (b) Given 4 intervals (1,4), (3,5), (0,6) and (5,7) each representing start and end times of an activity requiring the same resource. Find an optimal solution of non-overlapping intervals using the following strategies (i) earliest start time first. (iii) earliest finish time first. (6) (b) (i) Why does the greedy al.gorithm fail for weighted interval scheduling? (e) Can a graph with a cycle have a Topological ordering? Justify your answer with a short example. (3) (ii) Give an example where selecting the interval with the earliest finishing time does not yield the optimal total value. (5) (D Which algorithm design approach gives optimal solution for the following : (c) Will Dijkstra's algorithm still give the shortest path between two vertices if the edge weights are allow.ed to be negative? If yes, justify your answer with an argument. If not, give an example. (i) Binary Search (ii) Interval Scheduling Problem (iii) Subset Sum Problem 7. (a) Give a recurrence relatiofi for the following functions : (5) (g) Sort the following list of integers using Radix (i) void func(int n, char source, char aux, char dest) { cout << "Move disk 1 from " << source << " to " Show the state of the array after each digit-level sorting pass. (3) (h) (i) What is an adjacency matrix? (ii) State one advantage and disadvantage of representing a graph using adjacency matrix. (i) Define strongly connected graph in the context of directed graphs. Draw a strongly connected graph with five nodes. (3) 0) (i) What is the selection problem? (ii) What is the least number of comparisons to find the minimum and maximum element in an array. (3) (c) Consider the following recursive algorithm to find an optimal 5 schedule for the weighted interval scheduling problem : If j - 0, then return 0 2. (a) Explain how Strassen's algorithm is better than traditional matrix multiplication. (3) (i) Explain why this algorithm takes exponential time to run in the worst case. (b) Match the following sorting algorithms (Column A) with their correct properties (Column a). A. Count Sort 8. Insertion sort C. Merge Sort D. Quick Sort