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

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

I ? -
g I - .7. , .,. ..,? .,;..,.,5. .mm? .. . I m ..,.I--.......-..u-w-- - r...
V(g).
\ This question paper contains 4ipn'nted pages.
. .
Your Roll No. ......................
Sl. No. of Ques. Paper : 6367. F-6
? Unique Paper Code ? :2341401 I
Name of Paper ? :Design and Analysis of Algorithms
. Name ofVCourse :8 ..Tech in Compt?lter Science
Semester ? :IV
Duration ?: :3 hours
Maximum?Marks : 75 '
L(a)
(b)
(C)
. , '(d)
_?(e)
(f).
(h)
. (WeyaURoUNomthempmunedtatelyonreeeptof?wquafuonpaper)
Q.No.1 (35 marks) ls compulsory. Attemptfour questions from Q. No.
,.._._? _
Given a graph G= (V, E). Write an algorithm to determine If the graph Is acyclic.
Let P be a shortest path from some vertex 5 to some other vettext In a graph. if the
weight of each edge In the graph Is increased by one, will P still be a shortest path -
from s to 1?? Support your answer with appropriate arguments.
2toQ No. 7.
(4)
I (3)
Assuming adjacency list representation of graphs, discuss the time complexity of (3)
performing BFS.
Consider the following recurrence relatioh:
? i(n)= 2, , if n <='l
f(n)= f(n72) + n, Ifn > 1.
Write a dynamic programming algorithIn to compute f(n) above. ' ?
Do greedy algorithms always give optimal soution's? If not, give an example-
where the greedy algorithm does not always give the optimal solution.
Describn an algorithm that given n integers in the range 0 to k preprocesses its
? input and 'an'swers any query about how many of the n integers fall into range (a,
b] In 0( 1) time. Preproc'essing time should not be more than 9(n+k).
Prove that red black trees are balanced, i. e., If a red-biack tree contains n nodes.
then its height Is. O(log n)
Insertion sort can be. expressed as a recursive pI-oce?dure as follows. Given
A[l. n] we recursively sort A[l. .n- 11 and then insert element A[n] into the
sorted array A[l. .n- 1]. Write a recurrence relation for the running time of this
recursive version of Insertion sort and give time complexity of the algorithm by
solving the recm rence
? (4)
(3)
(4)
(5)
(4) "
Rrb

L? , ,
1
.7
I
I
?
I
l
I
7
3 . - .
6 67 7 i ?1
';1 (i) Analyze time complexity for the given algorithm (written in pseudo'code)
, X = 0;
. i 5 l; '
?1? , while( i < jn )
i = 2 * i;
X-H-;
}
0) State whether the sequence <20, 15, 18, 7, 9, 5, 12,. 3, 6, 2) a max?heap 6r not?
2.(a) ? Can we use Heapsort as the auxiliary sorting routine 'in radix sort? I ?
(b) Consider th; folloWin? Red-Black Tree: '
.k?.
Vlns?rt 7, 17 in the?givcn red-black tree. 'From _theV-resultant tree, obtained a?er
inscrtipg the two new nodes, delete'717 and then 7.
(c) What is the largast possible number of internal nodeslin a red-bl?cig tree with black-
?1
i
11 1 height k? What is the smallest possible numbcr of 'nodes?
I .
3.(a) 'Two key ingredients that an optimisation problem must have ih d?rdei'vfor dynamic .
, ? programming to apply are o'ptim?l subs?iucture and Overlapping subproblems. Expldin
I ' these'twp progenies.? Show that rod-cutting problem has bothrthgse properties.
(5) Determine an LCS of < l,0,0,1,0,1?,0,1' > and <0,1,:0,l_,l,"0,l,1,0>.
4(a) Give an adjacency?li?t represent?tion for a comp?let??binary tree?on 7 vertices.?
Give an equivaleht adjacencylmatrix representation. Assume that yeniccs are
numbei-ed from 1 to 7 as in a bi?ary heap.
(3).
(2)
(2)
(6)

~25 ' m 6367
(b) Find a minimum spanning tree fo_r the weighted graph shown beww using Prim s (4)
MST algorithm:
(c) Consider the following graph. (3) -
- i) Draw the resultant depth-?rst tree obtained on running DFS on?the
graph. Start your search with vertex B.
i) - 7 Show the discovery ahd ?nishing times for each vertex, and show the
classi?cation of' each edge
5. (a) Given an adjacency list- representation of ?a directed graph. Give an efficient (5)
algorithm to compute the transpose. Analyse the runnin n1g time of your algorithm.
Transpose of a graph G? (V, E) is the graph GT? - (V, E)
(b) Find a shortest path from vertex D to vertex A in the following graph by ? (5)
? carefully following the steps of Dijkstra? s aigorithm. '

6.(a)
(b)
(C)
7.(a)
_m
Fail? < o, l , l,2,3,4,2,2> -
_ .. ... ... . .,..-.? umm- yw-?r .
.=.w-" . .?
w
. I
?:
,1
?
5.
.l
1
.5
,,
Show that the second smallest of n elements can be faundfwith n +_ [lg n] - 2 ? (4_)
- comparisons in the worst ease. _-' ?
What do you undemandby a stable algorithm? Is the following code o'fcbunt (3) '
? sort stable? Expiain why/why not. In case it 'is (mstable rwhat change will make it
stable? ? ? ? H ? ? ' '
. count sort(A,B,k) . f . ?. . ,
Ir?fori=0tok ' ?_ . ? . . V
V 'C[i]=:0 ? '
forjf??l to A.Iength
CIAU]]=C[AU]]'+1
for i=1 t0'k
_ .Cii1=C?]+C[i-l] _ _ ,
forj?l_toA.|e,ngth 2 4-7 -' ' ' x ' " . ' ? '- ' '
.qumkAm ? ' g ' ..'. 7 ? 19
CIAUH = CIAUH - 1' .- ' .. ? -
Consider s'orti'ngn numbers stored in array A? using Selection Son. Why does it _ ' (3)-
need torun for bnly the ?rst 'n - 1 elements, rather than for allzn elements? Give '
the bcst-caseand worst-case runningtimes of Selection 5011 in e-n'otationL
Let A[1 .. n] be an array of n distinct numbers, Ifi < j and A[i] > A[j], they the "(2+3)
._ Vpair'(i,r j) is called an inversibn'ofA. ' . - , ? ? '-
i) " List the ?ve invetsions of the array <2, 3,,8, 6, D. , . _ ,
it) What array with elements {1, 2, n} has the most inversions? How
_ - many does it?have?? _ . __ ? e. ?
Give a pattern beginhing with A and using only letters from the set {A,B} that ?(5) '
'would have the following failure, indexes (for KMPt?owchan construction) ?
Hod .