Download DU (University of Delhi) B-Tech (Bachelor of Technology) 3rd Semester 1568 Discrete Structures Question Paper
IDIDIIADD
u
DID!
,.-_L_.!., .J A D D D
D
' " . 1?4.
3?; Wk . ?1 ~ wm \v
,1.
LN u
' This question paper contains 4+1 printed pages]
Roll No.
S. No. of Question Paper : 1568
Unique Paper Code : 2341303 . F-3
Name of the Paper : Discrete Structures ?
Name of the Course : B.Tech. in Computer Science
Semester : III
Duration : 3 Hours > - Maximum Marks : 75
(Write your Roll No. on the top immediately on receipt of this question paper.)
Section A is compulsoi'y.
Do any four questiohs from Section B.
Section A
1. .(a) A collectionof 10 electric bulbs contains 3"defective ones :
. (1?) hi how ma?y ways can_a sample of fdur bulbs. be selected ?
(i1) ' In how many ways cah a sample of four bulbs be s?lected which contains two
good bulbs and Zdefective ones ? ' ., , , 1+2
(1)) Suppose f](x) iS O(?g1(x)) and f2(x) iS chz(x)) ?ien show that (f1(X) + f2(X)) is
O(max(g1(x), 32(x)))? . i 3
? (c) Evalu?te the sum: -? . . 3
h?
ll
??
. 151.0.
D
DID!!!
IDDD)
D I I D I?LL?I?LI?I?L?LLI D D D D I I!
(2) 1568'
((1) Show that : I _ 2
??>(q?>r) and q?>(pvr)
are logically equivalent.
(e) Detemiine tho discrete numegio function of the genorating function : 4
A(Z) = 22/(4 ? 42 + zz).
(f) Prove that every bipartite graph is 2-colorabl_e. ' 2
(g) Using master theorem, ?nd the sqution to the recurrence : 3
4T(n/2) f n? = T(n).
(h) Consid?r a set A = .{-2, 7, 14, 28,_ 56, 84} and the relation a 5 b if and only if a
divides b. Give the Hasse diagram for the Partial .o-rderr?set (A, 3)., 3
(17 How many edges are there Jinanvunc?iirected graph with ??9.V":1.1_i??5 of degree ?7, four
_ _ vortice? of degree ?, gpdv fou't vcrtice? of degree 6'? . - -. V ? ' 2 V
(j) Show that a full m-ary baianced tree of height?h has; more mmmh-l leavo?. 3?
V V (10 Let {AI 55in 'and IBI= in where in?> n. Give the nu?rhber' of on??o??one ftmotions,
f:A-??)Bthatcanbe.de?ned? ? f ' . 2
(I) Show_ that for a graph to be'planar it should at least one vertex Vof degree 5 or
(m) - Write the-contrapositive and ittyerse of the following statements : ? " 2
If you try hard, then you will win.
I
DDDDDD
L_L.)___D I D
p I p L
|JJIDDDDDD|
(a)
(b)
(C)
('0)
( 3 ) 1568
Section B
F ind the number of integers between 1 and 250 that are divisible by any of the integers
L3,5md1 . 4
?Let X '= '{1, 2, 3, 4, 5, 6}, and de?ne a relation?R on X as R = {(1, 2), (2, l),
(2, 3), (3, 4), (4, 5), (5, 6)}. Find the re?exive and transitive closure of R. 3
Prove that n3 ? n is divisible by 3 for ?hy integer n 2 0., 3
Let ?a? be a numeric function such that : ' , 4
2 ' OSrS3.
a, =
2*'$5 -.?r2~4
' ?('1') Deten?nine-?A'a
(b) h
(C) .
.the same score'on the ?nal exam, if the exam
(i1). Va.
~F 1nd the total solution of the recurrence?relation : 7 _ . t 3 . 4
. an. + 4%?3 7?? 7. Wheteiao = 3.
.How mahy students must be in a class to guarantee that at least two studentsteceive
isgradedon ?a scale from 0 to 100? V
:vY,1?
> , points ? I _ .t ' 2
P10
DDDDDD
Dllb?i
D
IDDDDDDDDDDI
I p .. L L_LLJ
(0)
(b)
(C)
(a)
(b)
(c):
(a)
V?) .'
(c)
( 4 ) 1568?
Draw the graph K6 and answer the following questions : 1+3
(i) What is the degree of each vertex ?
(ii) Is K6 planar ?
A connected planar graph G has 10 vertices each of degree 3. Into how many regions
?does a representation of this planar graph split the plane ? 4
How many leaves does a regular (full) 3-ary tree with 100 vertices have ? , 2
Draw graphs each having six vertices such that : . 4
(1) Graph is Hamiltonian but not Eu?lerian
(ii) Graph is Eulerian but not Hamiltonian,
Show that the sum of degree of all vertices in ?G is twice the.? number of edges
in G} ' A ? a ' i ' I 1? 3
What is the condition for Km n t6 have an Euler path or circuit ? Justify your
answer. h , . 3
Use the insertiqn sort algorithnt to sort the list 2, i4, 9, 13, 12. - t -' .3
Determine whether?each of m; ?ihctions 2"? and 22" is C(27). . 4
I Using substitutibrt method, prove that T(n) is_ O (n lg n) given that : 3
T(n) =_ 21(1) + n.
2
I
)DDDDDDDDDDDDI
(a)
(b)
? (C)
l 5 ) l 568
Show that (p ?-> q) A (r ?-) q) q: (p v r) ?> q are logically equivalent using the laws of
logical equivalences. 4
Show that :
(p A q) ?> (p v q)
is a tautology with the help of truth table. ' 2
Show that the premises ?If is not sunny this aftemoon and it is colder than yesterday;?
?We will go swimming only if it sunn'y;? ?If we do not go swimminggtthen we will
take a canoe trip?; and ?If we take a canoe trip, then we will Be home by sunset?
lead to the conclusion??We will be home by sunset?. - 4
5 _ ' ' 2,000
This post was last modified on 31 January 2020