Uttar Pradesh Technical University (UPTU) 2009-1st Sem M.C.A --ester- Discrete Mathematics - Question Paper
MCA
(I sem) ODD semester theory exam
Discrete Mathematics
Printed Pages: 8 MCA 114
(Following Paper ID and Roll No. to he filled in your Answer Book)
Roll No. |0 q| 2-1 <\
PAPER ID: 7304
Mo
(SEM I) ODD SEMESTER TTHEORY EXAMINATION 2009-10 DISCRETE MATHEMATICS
Time:?, Hours I f Total Marks: 100
Note : Question - Paper carries three sections. Read the instruction carefully and answer accordingly.
1 Attempt all parts of this section :
(i) This question contains 10 multiple choice 10x1=10 questions. Select the correct answer forv each one as per instruction.
(a) Consider (X, Y, f) is a morphism, where
/ :X F. If image set of f is (j> then / is
(i) an empty function
(ii) an identy function
(iii) a surjective function
(iv) an injective function.
(b) Let I+ be the set of positive integers and R be the relation on /+ defined by xRy iff 2x < y +1. Then which ordered pair belongs to R (0 (2, 2)
(iii) (6, 15)
(iv) (15, 6)
(c) Let / be the set of integers and R be the relation on / defined by x R y iff |ac - ,y| = 2. Then the
relation R on the set I is :
(i) Reflexive
(ii) Symmetric
(iii) Transitive
(iv) None of above
(d) Let (X, *) be a group, where * is the multiplication operation on X. Then for any x, y e X which one is true 9
00 (x'V1 =x
(ii') (xy) 1 = y x
(iv) None of above
(e) The number of minterms in the k-map of
3 variable boolean function are :
(i) 4
(ii) 6
(iii) 8
(iv) 16
JJ-7304] flllllHIIIII! Illlllll 2 IConfd...
: a *
(i) Regular graph
(f) Graph shown below is an example of
(ii) Planar graph
(iii) Bipartite graph
(iv) None of above
(g) An undirected graph G = (V, E) is complete iff:
(ii) \E\ = n (n -1)
(iii) |jB| = n(n-l)/2
(iv) |j| = <|>.
(h) The truth value of the formula (P->Q)v~(Pe~Q) if p and Q are true will be
(i) True
(ii) False
(iii) False and True both
(iv) None of above.
IllllilllUllillllUllllllllll 3 [Contd...
* .' j - 3 0
(i ) Which one of the following formulas is true ?
(i) (P->Q)o(~PaQ)
(ii) (P->Q)(~PvQ)
(iii) (PoQ) o (P -> Q) v (Q P)
(iv) (PaQ)o-(PaQ)
(j) Suppose we have n distinct letters, then total number of words can be formed with those n letters are :
(i) n
(ii) n(n-\)
(iii) n-(7i-l-(/t-2)...... 3-2-1
(iv) n(n~l)!2
(ii) State True / False : 5x1=5
(a) For any finite set X, <j>ep(X) where p(A") is the power set of X.
(b) A graph is bipartite iff it contains no odd cycle.
(c) Master theorem is used to solve the recurrences and return the solution in asymptotic bounds.
(d) The time complexity of the function that multiply two matrices of order n can be less than o(n3)
(e) Solution of the recurrence T(n) = 2T(n /2) + c for n> 2 is Q(n log n).
(iii) Fill in the blanks : 5x1-5
(a) If S and T are two sets not necessary disjoint then |SuT|=|S| + |rl---
(b) A binary tree that has n nodes may need an array of size up to - for its
representation.
(c) A regular graph with vertices of degree k is called as--
(d) nC =--
n
(e) (P->Q)aP
Attempt any three parts : 10*3=30
(a) Consider a relation R~{(x, y) | x, y e /+ and (x - is divisible by 3 j. Find the set of equivalence classes generated by the elements of set j+ .
(b) Let G be an Abelian group and N is a subgroup of G Prove that GIN is an Abelian group
(c) Consider a set X = {a, p, y}. Draw the Hasse
diagram of the poset (p(X), c:), where P(X) is the power set of X
(d) Prove that the formula Bv(B->C) is a tautology. 7304] llllllilllllll S [Cont,I...
(e) A box is filled with three blue balls, three red balls and four yellow balls. Eight balls are taken out one at a time. In how many ways can this be done. (Assume that balls of same color are indistinguishable).
Attempt any five parts selecting are from each 10x5=50 questions :
3 (a) For given sets X = 2}, Y = {a, b, c} and
Z = {c, d}, find IXxY)r(XxZ)
(b) Prove the following property of Fibonacci numbers
.......+ fn=fnfn+V
where f0 = 0, fx = 1 and ft = + ft_2 for ft 2
4 (a) Let /: G H be a group homomorphism, prove that
Ker (/) is a normal subgroup of G.
(b) Prove that ({0, 1, 2, 3, 4}, +5>*g) is a finite
field, where +5 is addition modulo 5 and *5 is multiplication modulo 5 operators.
5 (a) For a given truth table obtain the simplified Boolean functions and /2 is sum-of-products and products-of-sum forms.
| |||||||||||||||||||||||||||||||||||||||||||||
|
(b) Show that a bipartite graph is 2-colorable. |
6 (a) Show that B - E |s a valid conclusion drawn from
the following premises :
and ~ C
(b) Prove that following argument is valid using predicate logic :
(i) All dogs are barking.
(ii) Some animals are dogs.
/:. Same animals are barking.
7 (a) Solve the recurrence T(n) = 2T(n/2) + n for
n 2 and n is a power of 2.
T
number sequence is-:- The Fibonacci numbers
1 m
\-x~x
are defined by the recurrence f ~ f + f a for
J 'n 'n-1 *n-2
n> 2 where f = q arld A = 1
|
Attachment: |
| Earning: Approval pending. |
