Design and Analysis of Algorithms — DU B.Sc. (Prog) Physical Science courses pertaining to Computer Science Previous Year Question Papers

7. (a) Explain the Radix Sort algorithm in detail and apply it to sort the g,iven `1ist : Show each pass and the final sorted output. (b) Solve the subset sum problem using dynamic programming for the set A = [2, 3, 7, 8, 10] and i.ntended sum = 11. (8) (Prog. / B.Sc. a?rog.) 4. Parts of a question must be.answered together. 1. (a) What are the two key factors that decide whether dynam'ic programming is applicable for an optimization problem or not? (3). (b) Consider the undirected graph G(V, E): (3) Check If the Graph is bipartite and give the two vertex sets. (c) Briefly Explain the Divide and Conquer technique with an example of algorithm that uses this approach. (3) (d) Show that at most 3* [n/2.] comparison.s are sufficient to find both the minimum and maximum number in a given array of size n. (3) (b) Consider Interval Scheduling problem where we are given a resource and a set of requests ea.ch having a start time and finish time. . The goal is to maximize the number of requests scheduled. Determine whether the followin.g greedy strategy gives an optimal solution for the above problem or not: "Select the requests. with fewest number of incom.patible requests." (8) " ty' 6. (a) Sortthe following listusingMerge sort and show Fl i* all division and merging steps with diagrams: Give the best case and worst-case time complexity. (b) A hash table has Size = 11 Use the division method h(k) = k mod 11 Insert keys in this order: 27, 18, 29, 28, 39, 13, 16 Resolve collision by Linear probing : Show the final position of keys in hash table witb index. (8) (b) A thief enters a house carrying a bag of maximum capacity of 60 Kg. There are 5 8 items in the house with the following weights and values. What items should he take. in order to maximize the value (fractional weights are also allowed). (e) Define the following terms in the context of graphs giving suitable examples of each: (i)- Acyclic graph (ii) Weighted graph (3) Item Weight Value (I) Prove: If a graph is bipartite then it cannot contain an odd cycle. (3) Secondary clustering in hashing. (3) (h) What is the recurrenc.e relation for the following algorithms : (i) Insertion sort 5. (a) Show the step by step execution of Prim's algorithm to find minimum spanning tree (MST) of the given graph : (ii) Merge Sort (iii) Counting sort (3) (i) Explain Randomized Quick Sort algorithm for sorting a list of numbers. How does the use of random pivot selection affect.the time complexity compared to normal Quick sort? (3) What is the cost of MST generated? (7) ¢) What is collision in hashing? Name any two collision resolution techniques: (3) 2. (a) Use strassen's Algorithm to multiply the following two matrices : (7) (b) Consider the undirected graph G(V, E) with vertices (8) V = {A, 8, C, D, E, F} and edges (i) Draw the graph G. (ii) Determine whether the graph is connected or disconnected. (iii) If it is disconnected, find all its connected components.