RTU 2016 Question Paper Semester IV Computer Science and Engineering Discrete Mathematics Structure

,l I *)>*rr,
o
1e
fot"l nfo of Pages:p

F{ 4E4t6L
\0 B.Tech.IV-Sem(Main&Back)Exam;June-July2016
F{
+ ComPutei Science & Engineering
frl 4CS2A Discrete Mathematicll.ltructures
+ Common with CS,IT
Maximum Marks: 80'
Time: 3 llours 26
Min. Passing Marks (Main & Back):
Min. Paising Marks (Old Back): 24

'v Instructions to Candidates:- .. ,- r:
setecting one que-s.tion from each unit' All
;;;;;-;;r--trn, nunrtions, Sjematii diagrams must be shown
carry ryo,t,,,
Questions ';^
wherever necessary. ,+ny data
you Tuet *itting iurtably be assumed
and

stated clearlY.
must be stated clearly'
units of quantities used/ calculated
Useoffollowingsupportingmaterialispermittedduringexamination.
(Meniioned in form No'205 )
2

UNIT-I
Q.1 (a) Among integers 1 to
1000 r: -:^:,^r^ L-.2 ? t8l
(i)Howmanyofthemarenotdivisibleby3norby5norbyl?
by 3?
(ii) Uo* not divisible by 5 or 7 but divisible
"'u"y
(b)(i)Letthereare5separatesdepartmentsinadepartmentalstoreandthelotal have
that one of the departments must
number of employe ** zi. Show
" t4l
atleast 8 emPloYees' t4l
(ii)'"o1'.,*'tj-,?friix;
uncountabre sets

iUl Mod functions and Div functions
OR
[4]
" Q.1 (a) Prove that A-B = A n B'= B'
n A'
of subsets t4l
(b) Consider the following collection
{Ar,Az,A3} of asetA={ 1'
2'3'4'5'6'7'8'9' 10}
10}l
iul [t1,6, g],12,3, 81, {4, 5' 7'
tbl {li, {2,4,8}, {5,7,9}l and
10}l
i.j itt, s), 12,3,8\, {4,5,6,7,9'
a partition of a set A
Determine which one is

Page 1 of4
[6e601
14847611

(c) Let f, g, h be mapping from N to N when N is the set of naturals such that
iseven
f(n) = n + l, g (n) = 2n, h (n)={:'' I8l
[. n is odd
(i) Show that f, g and h are functions
(ii) Determine fof, fog, hog and (fog) oh
Where 'o' stands for composition of functions

Q,2 (a) Define equivalence Relation. If R and S be two equivalence relations in a set A,
then prove that R n S is also an equivalence relation in A.
tgl

(b) Ler A=[l o 'l ,ro ,=[l ;l
Lo r ol lo .]
Find AO B and B O A, if defined
t4l
(c) What is closure of relations? Let A = {1,2,3, 4} and R = {(1, 2), (2,3), (3, 4) be
a relation in A. find its reflexive closure, symmetric closure and transitive
closure.
t4l
OR
Q.2 (a) An equivalence relation R on a set A decomposes A into equivalence classes
which are either distinct or completely overlapping and the set A is the union of
such distinct equivalence classes.
t8l
(b) I.et x - { 1, 3, 5,7, 15,21, 35, 105} and R be the relation 'l' (divides) on the set
x then x is the poset. Draw the Hasse diagram of the given poset. Determine the
following. t8l
(i) I UB of 3 and7
(ii) GLB of 15 and 35
(iii) Greatest and least element of X.

Q.3 (a) Define the following with examples. t12l
(i) Direct proof.
(ii) Proof by contra-position.
(iii) Prof by exhausting cases.
(iv) Proof by contradiction.
(b) Sort the list x = 134, 13,21,3,891 using bubble sort algorithm. 14)

[4E4t6L] Page2 of4 [6e601

OR
Q.3 (a) Prove by mathematical induction that 6n*2 * ,Zn+l is divisible by 43 for each
positive integer n. t8l
(b) What is Linear and binary search algorithm. Show the correctness proof of linear
and binary search algorithm. t8I
UNIT-IV
Q.4 (a) Prove that the number of vertices of odd degrees in an undirected graph is always
even. l4l
(b) If G be a cyclic- free (acyclic) graph with n-vertices and r connected components,
then G has n-r edges. t4l
(c) Define Adjacency matrix and Incidence matrix with example. t8l
OR
Q.a (a) (i) Give an example of connected graph that has l4l
(a) A Hamiltonian cycle but no Euler circuit
(b) A Euler circuit but no Hamiltonian cycle
(b) (ii) What is the length of shortest path between the vertices a to z in the
following weighted graph I4l

,i t

(c) (i) A woman bracelet is formed by placing three beads- red, white and blue, on
a circular pieoe of wire. Bracelets are considered equivalent if one can be
obtained from'other by planar rotations. Find the pattern inventory of these
bracelets. l4l

[4841611 Page 3 of4 [6e601

(ii) By using Kruskal's algorithm determine a minimal spanning tree in the
following graph. 141

Q.5 (a) Prove that (- p^q) -+ t-(q-+p)l is a tautology with constructing truth table. tSl
(b) Obtain the principle disjunctive normal form of (pnq) v (-pnr) v (qnr) by
constructing truth table. tSl
OR
Q.5 (a) Translate each of these statements into logical expressions using predicates,
quantifiers and logical connectives. t6l
(i) No one is perfect
(ii) Non everyone is perfect
(iii) All your friends are perfect
(iv) One of your friend is perfect
(v) Everyone is your friend and perfect
(vi) Not every body is your friend or someone is not perfect.
(b) Explain the converse, contra positive and inverse of the given implication "If it is
snows today, then I will stay at home. l4l
(c) Test the validity of the argument.
"If there was a ball game, then travelling was difficult. If they arrived on time,
then travelling was not difficult. They arrived on time. Therefore, these was no
ballgame. t6l

l4E4L67l Page 4 of 4 [6e60]