Download DU (University of Delhi) B-Tech 4th Semester 2361 Design and Analysis of Algorithms Question Paper

FirstRanker.com

Sr.No. of Question Paper : 2361

Unique Paper Code : 12341401

--- Content provided by FirstRanker.com ---

Name of the Course : B.Tech. in Computer Science

Name of the Paper : Design and Analysis of Algorithms

Semester : IV

Duration : 3 Hours

Maximum Marks : 75

--- Content provided by FirstRanker.com ---

Instructions for Candidates:

1. Write your Roll No. on the top immediately on receipt of this question paper.
2. Question 1 (35 marks) is compulsory.
3. Attempt any four questions from Question 2 to Question 7.

1. (a) Comment on the following statement and support your answer with appropriate arguments/example: An already sorted array is the best case input for all sorting algorithms. (3)
   

   --- Content provided by FirstRanker.com ---

   (b) Assuming adjacency list representation of graphs, discuss the time complexity of performing DFS. (3)
   (c) What is the significance of having the input data uniformly distributed for applying bucket sort? What happens if this does not hold? (3)
   (d) Assuming that all elements are distinct, what are the possible locations for the smallest and largest elements in a max-heap? Is an array sorted in reverse order a max-heap? (3)
   (e) Give an example to show that the fractional knapsack and 0-1 knapsack problems may yield different solutions for the same input instance. (3)
2. (a) With the help of an example, show that the following greedy algorithm for the activity selection problem is not correct:
   

   --- Content provided by FirstRanker.com ---

   While there are activities left
   Select the activity with shortest span (fi - si)
   Remove the activities that overlap with the selected activity (3)
   (b) Consider the following pseudocode for calculating a*b (where a and b are positive integers)
   Pow(x,y)
   

   --- Content provided by FirstRanker.com ---

   if y=1
   return x
   else
   z = x*x
   ans = pow (z, floor(y/2))
   

   --- Content provided by FirstRanker.com ---

   if y is odd
   return x * ans
   else
   return ans
   Assuming that multiplication can be done in constant time, give the asymptotic run time of the above algorithm. (3)
   

   --- Content provided by FirstRanker.com ---

   (c) Consider the following implementation of bubble sort. Comment on whether or not it is stable. If yes, support your answer with appropriate arguments, otherwise indicate how can it be made stable.
   boolean swapped = true;
   int j = 0;
   int tmp;
   while (swapped) {
   

   --- Content provided by FirstRanker.com ---

   swapped = false;
   for (int i = 0; i < arr.length - j; i++){
   if (arr[i]>arr[i+1]){
   tmp = arr[i];
   arr[i] = arr[i+1];
   

   --- Content provided by FirstRanker.com ---

   arr[i+1] = tmp;
   swapped = true;
   }
   }
3. (a) Let P be a shortest path from vertex s to another vertex t in a graph G(V,E). If the weight of each edge is multiplied with a constant c (i.e., w(e) = w(e) *c for all e ∈ E where c > 0 is a constant), will P still be a shortest path from s to t? Support your answer with appropriate arguments. (3)
   

   --- Content provided by FirstRanker.com ---

   (b) For an unweighted graph, the BFS traversal technique performed with vertex s as the source would yield the minimum distance between s and any other vertex v reachable from s. Would the same hold for a weighted graph? If yes, justify your answer; otherwise give a suitable example to disprove. (4)
4. (a) Give pseudocode for Right Rotation operation used for balancing Red Black trees. Discuss its time complexity. (3)
   (b) When does insertion sort show its best case and worst case behaviour? Give its time complexity for each case. (3)
5. (a) Using an O(n²) algorithm, find the longest monotonically increasing subsequence in the following string: djbmhtpwz. (4)
   (b) 1000 tonnes of wooden planks are to be dumped in store rooms. Each store room has a specified capacity indicating the number of planks it can store. The goal to store the planks in rooms so as to minimize the number of rooms occupied. Show that this problem has (i) optimal substructure (ii) greedy choice property. Give an efficient algorithm for the problem and discuss its time complexity. (4)

--- Content provided by FirstRanker.com ---

6. (a) What is the minimum and maximum number of elements that a heap of height h can contain? (3)
   (b) Let e be a maximum weight edge on some cycle of G = (V,E). Prove that there is a minimum spanning tree of G' = (V,E-{e}) that is also a minimum spanning tree of G. That is, there is a minimum spanning tree of G that does not include e. (4)
7. (a) Give the recurrence relation for Merge sort and thus find its time complexity. (3)
   (b) Argue the correctness of radix sort algorithm. (3)
8. (a) Give a procedure to sort n integers in the range 0 to n² - 1 in O(n) time. (4)
   

   --- Content provided by FirstRanker.com ---

   (b) Consider the problem of finding i order statistic using Randomized Select. Let 0.5 < α < 1 be a constant. What is the probability that after the first iteration the size of the subarray in which the element being looked for lies is at most α times the size of the original array? (3)
9. (a) Insert key 65 in the following red-black tree (3)
   (Diagram of Red-Black Tree would be here)
10. (a) You are given n numbers each of which is either 0 or 1. Give an O(n) algorithm to sort these numbers and discuss its run time. (3)
    (b) Show that the longest simple path from a node x in an RB Tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf. (3)

--- Content provided by FirstRanker.com ---

11. (a) Find the failure indexes for the following pattern: banananobano (4)
    (b) Find the MST of the following graph using Kruskal’s algorithm. (5)
    (Diagram of Graph would be here)
12. (a) Find the strongly connected components in the following graph. (5)
    (Diagram of Graph would be here)

--- Content provided by FirstRanker.com ---

FirstRanker.com