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

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

[This question paper contains () printed pages]
\
Sr. No. onuestion Paper : 2361 F?4 You! Roll No
Unique Paper Code 1 2341401 l ?
Name 0fthe Course : B.chh. in Computer Science
Name of the Paper : Design and Analysis of Algorithms. . I 3:
Semester : IV
Duration : 3 Hours Maximurh Marks': 75
Instructions for Candidates
Write your Roll No. on the top immediately on receipt of this question paper.
Question 1 (35 marks) is compulsory.
Attempt any four questions from Question 2 to Question 7.
(a)
(b)
(C)
(d)
(6)
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)
Assuming adjacency list representation of graphs, discuss the time complexity
ofperforming DFS. (3)
What is the signi?cance of having the input data uniformly distributed for
applying bucket sort ? What happens ifthis does not hold ? (3)
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)
Give an example to show that the fractional knapsack and 0-1 knapsack
problems may yield different solutions for the same input instance. (3)
P.T.O.

2361
-0)
(g)
(h)
2
With the help of an example, show that?the following greedy algorithm for
the activity selection ptoblem is not correct : ? ' ?
While there'are activities left
Select the activity with shortest spari (ii i si)
Remove the activities that overlap with the selected activity (3)
v?
Consider the following pseudocode for calculating a"b (where a and b are
positive integers)
P0w(x,y)
if y=l
return x
else
2 = x*x ?
ans 7f pow (z, floor(y/2))
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)
Consider the following implementation of bubble 8011. 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;

M?W.. WP?Z?W-?Ili; ? '
2361
(i)
(k)
(a)
while (swapped) {
swapped: false;
j++;
for (int i = 0; i < arr.length - j; i++){
if (arr[i]>arr[i+1]){
tmp = arr[i];
arr[i] = arr[i+l];
arr[i+l] = tmp;
swapped = true;
} (3)
Let P be a shortest path from vertex 3 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 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)
For an unweighted graph, the BFS traversal technique performed with
vertex 8 as the source would yield the minimum distance between s and
any other vertex V reachable from 8. Would the same hold for a weighted
graph ? If yes, justify your answer; otherwise give a suitable example to_
disprove. (4)
Give pseudocode for Right Rotation operation used for balancing Red Black
trees. Discuss its time complexity. (4)
When does insertion sort show its best case and worst case behaviour ?
Give its time complexity for each case. _(5)
P.T.0.

2361
(b)
3 (a)
(b)
4. (a)
(b)
(C)
5 (a)
(b)
4
Using an O(nz) algorithm, ?nd the longest monotonically increasing
subsequence in the following string 5 dj b in} h t p w z . (5)
1000 tonnes of wooden planks are to be dumped in store rooms. Each store
room has a speci?ed 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 ef?cient algorithm for the problem and discuss its
time complexity. ? (7)
What is the minimum and maximum number of elements that a heap of height
h can contain ? (3)
Let e be a maximum weight edge on some cycle of G = (V,E). Prove that
there is a minimum spannin g 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)
Give the recurrence relation for Merge sort and thus ?nd its time
complexity. _ (3)
Argue the correctness of radix sort algorithm. (3)
Give a procedure to sort n integers in the range 0 to n2 - 1 in O(n)
time. (4)
Consider the problem of ?nding i'11 order statistic using Randomized Select,
Let 0.5 < (1 < 1 be a constant. What is the probability that after the ?rst
iteration the size of the subarray in which the element being looked for lies
is at most a times the size of the original array ? (3)

K 2361 5
(0) Insert key 65 in the follewing red?black tree (3)
1.?mhv'r"v- r?
NH 4 _. WMNHMW. ? . ,
6. (a) You are given 11 numbers each of which is either 0 0r 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)
(c) Find the failure indexes for the following pattern :
banananobano (4)
M
7. (3) Find the MST ofthe following graph using Kruskal?s algorithm. (5)
P.T.0.

2361 6
(b) ?Flind the strongly connected components in the following graph.
(5)
(2000)