Download DU (University of Delhi) B-Tech (Bachelor of Technology) 4th Semester 2341401 Design and Analysis of Algorithms Question Paper
1
I
1
1
Name of the Paper : Des1gn and Analysns of Algonthms
j 311:. "
Name bf course _ . z B .Te?h (Compu?sr Somme)
Smester IV
Duration of Examination: ThfeenI-Iours I ? "" I '
Maximum Marks : 75 marks
Instructions:
Question No I of 35 marks is compulsory
Attempt any?mr q11?st10ns from Q No 2 to Q1111 7 .
Number of Printed Sheets 1n Questmin Paper.
. W
1- : -
1?
??1.. .?
1
.3
WWW , ?WFSW1 ....*? G?WWF?FJHIIVW W 13%:de +1531! ,3
mi? 1' 3 11? ? ;?? w ' ,1. 1 *2";~, 41.1..1'1'H? '1
mm .
? Mia)" ?
(b), H
(C)
(d)
(e)
(f)
' , (g)-
(h)
(i)
2.(a)
(b)
3 .(a)
(b)
? a :s ?( ~\*?n;,, ??1 ? ?. \ 1* ?L! .4
???W?Rgmskv
.53
??ihem?nt?imeof the naive string matching ?algerithm. _
?of 11 operations is performed on a data structure The 1""-1 operation
is a poW?r 1<31? 3,? othcrvmm it costs 1 Use aggregate analysis to
dete?n ,1 the amortiSed cost per op?era?ti?6n.
Show that? there are at most [?lnodes of height h in a heap with n elements.
Whichproperties of e red?black tree e'an he violatea 'on deleting? a node?
(take two cases depending on whether the deleted node is fed or black) '
When does quick sort show its worst case behaviour? What iS the runtime in this
case?
Run the BFS and DFS algorithms on the following graph and show the
corresponding trees. . . 4
Give an ef?cient aigorithm? to ?nd both the minimum and maximum of a given
array of 11 elements.
Name and brie?y explain (i) greedy choice property (i1) optimal substructure
propexty.
Illustrate the operation of counting sort 011 the array <6,0,2,0,I,3,4,6,1,3,2>
innd the largest common subsequence 1n the following sequences:
=
Give the adjacency list and adjacency matrix representation of the following
graph: .
Sort the following character array using hedpsorti HEAPSORT
SHOW that the height of an n-node RBT is O(lg 11).
<2>
(3)
(3)
(4)
(4)
(4)
(5)
(5.)
(5)
(6)
(4)
(5)
(5)
4(a) * DeriVe an eXpression? for the nim'hne
S.(a) Consider a stack S on which the following Operatio'ns can be performed; (5)
.(b)' Name the design technique on which Kruskal?s m&??m?3-&l?0?m are based? (5)
" 6.(a) Are the following aigoritlu?s?) stable (ii) inQplace: Merge sort , Quick sort. ? (4)
(b) Show the ordering of vertices produced by topological sort When?run on the A (6)
?9??
o?nse'
0 Push (S, x): push objeet x onto the stack S ? ?
.' Pop (3): pop the top" element from? stack ?8? andretum the popped?bject
. Mul?pe? ($10: remove?ik 'top 653m from :S V '
Using the accounting method of ' analysis, dete ?Vjefthe 'amortiscd cost per
operation when a sequence ofn operations is perfomd'onthe stack. 8.
? What are the two ?ge?Ms meant for? ?Meh?tier-i thefundamental diffemepee in?
the way these algorithms wogl?, \ . '
Brie?y explain.
foilowing DAG.
7.(a) A man rides a bike between 2 cities located m kilometres apart. His tank needs to (5) ,?
be re?lled a?er every n kilometres. There are p ?le! Stations s1, 32, ....... , sp "along 7?
the way. The distance between a station si and- its previous station s? is given by ;
d(si). The distance between; the starting point .a?hd?ihe ?rst station is d(sl) ?and? 0_< ;
(1(a): nvfor ?all i. If- the man starts with a full tank, suggest how he-vca?n minimize E
W"?Mm?"3?"???fe"z'=WV-y :"?v: 413.101?? ; , ';;?;v:.t-:L~-?. 4, . -. ?- ~
? Elli??ps 3s; 'V
i
$m' Dams toi?k??ama km The mmmmm? (5)
" "?7: 11mg: ape-ti- item's to check 15mm. The? weight ?qnd
~*~3w a? rag ii; Ely Sugg??t???w h? ?an
. . . . N istb'??nto his bag. '
1?.
Urwrmawh,? .3,? 5?
This post was last modified on 31 January 2020