M.C.A-M.C.A 1st Sem DISCRETE MATHEMATICS (University of Pune, Pune-2013)
[4366]- 102
F.Y.M.C.A. (Engg. Faculty)
DISCRETE MATHEMATICS
(Semester - I) (2008 Pattern) (510902)
MAY 2013 EXAMINATIONS
Time: 3 Hours] [Max. Marks :70
Instructions to the candidates:
1) Answers any three questions from each section
2) Answers to the two sections should be written in the two separate answer sheets.
3) Figures to the right side indicate full marks.
4) Assume Suitable data if necessary.
SECTION I
Q1) a) It was found that in FY out of 80 students 50 know „C‟ language 55 know
“JAVA” and 25 know “COBOL” while 8 did not know any language,
Find:
i) How many know all three languages.
ii) How many know exactly 2 languages.
[6]
b) Prove that 5+10+15+…………..+5n=5n(n+1)/2 [6]
OR
Q2) a) Prove the following by using the Venn diagram
i) A ∩ B C = (A ∩ B) (A ∩ C)
ii) (A – B ) - C= A - ( B U C)
[6]
b) Obtain the C.N.F. & D.N.F of the following:
i) p < > q (~p v ~ q)
ii) (p v ~q) > q
[6]
Q3) a) Write the following statements in symbolic form, using quantifiers.
i) All students have taken a course in communication skills.
ii) There is girl student in the class who is a sport person.
iii) Some students are intelligent, but not hardworking.
[6]
b) Find the logical equivalence form of the following:
(p < > (q v r)) ~ p
[5]
OR
Q4) a) For the universe of all integers, let P(x), Q(x),R(x), S(x) and T(x) be the
following statements:
P(x) : x>0
Q(x) : x is even
R(x) : x is a perfect square
S(x) : x is divisible by 4
T(x) : x is divisible by 5
Write the following statements in symbolic form:
i) At least one integer is even.
ii) There exists a positive integer that is even.
iii) No even integer is divisible by 5.
iv) There exists an even integer divisible by 5.
v) If x is even and x is perfect square, then x is divisible by 4.
b) Functions f,g,h are defined on a set
X= {1,2,3,} as
f = {(1,2),(2,3),(3,1)}
g ={(1,2,)(2,1),(3,3)}
h = {(1,1),(2,2),(3,1)}
i) find fog,gof are they equal?
ii) Find fogoh and fohog.
Q5) a) Among 130 students, 60 study Mathematics, 51 study Physics and 30 study both
Mathematics and Physics. Out of 54 students studying Chemistry, 26 study
Mathematics, 21 study Physics and 12 study both Mathematics and Physics. All
the students studying neither Mathematics nor Physics are studying biology.
Find.
i) How many are studying Biology?
ii) How many not studying Chemistry are studying Mathematics but not
Physics?
iii) How many students are studying neither Mathematics nor Physics nor
Chemistry?
b) Two dice are rolled together. Event A denote that the sum of the numbers on the
top faces is even and event B denotes that there is a 4 on at least one of the top
faces. Find P (A U B) and P (A ^ B).
OR
Q6) a) Suppose repetition are not possible
1) How many three digit numbers can be formed from six digits 2, 3, 4, 5, 7, & 9?
2) How many of these numbers are less than 400?
3) How many are even?
4) How many are multiple of 5?
b) Explain the following terms:
1) Rule of Product and Rule of Sum
2) Sample space, sample point, event with example.
SECTION II
Q7) a) Use Warshall‟s algorithm to find transitive closure of the relation
R=(1,2)(1,3)(1,4)(2,3)(2,4)(3,4) on A={1,2,3,4}
b) Use Warshall‟s algorithm to find transitive closure [5]
OR
Q8) a) Let the functions F and G will be defined by
F(x)=2x+1 and G(x)=2x -2
Find
i) gof (a+3)
ii) fog (a+3)
iii) fog (5)
[5]
b) Determine whether each of these functions from {a, b, c, d} is it self is one – to – one.
f(a)=b, f(b)=a, f(c)=c, f(d)=d
f(a)=b, f(b)=b, f(c)=d, f(d)=c
f(a)=d, f(b)=b, f(c)=c, f(d)=d
[6]
Q9) a) Define the following terms:
i) Regular graph & full bipartite graph.
ii) Isomorphic graphs
iii) Complete graph
iv) Hamiltonian circuit
v) Simple graph and Multigraph
vi) Eulerian Circuit
[6]
b) Consider the following graph and find out incidence matrix and Adjacency matrix of a graph
OR
Q10) a) Draw the following graphs:
i) Complete graph with 4,7,10 vertices.
ii) Simple graph with 6 and 7 vertices
b) Determine whether the following graphs G = (V, E) and
G* = (V*, E*) are isomorphic or not.
G = ({a, b, c, d}, {(a, b), (a, d), (b, d) (c, d), (c, b), (d, c)})
G* = ({1, 2, 3, 4}, {(1, 2), (2, 3), (3, 1) (3, 4), (4,1), (4, 2)})
Q11) For the following set of weights, construct an optimal binary prefix code. For
each weight in the set give corresponding code word:
i) 8, 9, 10, 11, 13, 15, 22
ii) 5, 7, 8, 15, 35, 40
Q12) a) Explain the Dijkstra‟s algorithm with example.
| Earning: ₹ 7.50/- |
