Autonomous Colleges 2012-2nd Sem Master of Computer Applications (MCA) Discrete Mathematics, MCA ester, Government College of Engineering, Aurangabad - Question Paper
Government college of Engineering, Aurangabad
(An Autonomous Institute of Government of Maharashtra)
MCA End semester examination May-June 2012 MCA109: DISCRETE MATEMATICS
Time: Three hours Max Marks: 60
"Verify the course code and check whether you have got the correct question paper" N.B.:-
1. All questions are compulsory.
2. Figures to the right indicate full marks.
3. Assume suitable data if necessary and state it clearly.
4. Use of non programmable calculator is allowed.
Q. 1 Attempt any two
(a) State the principle of mathematical induction and hence prove that
1+2+3+.....+n=n 1 , for all n>0 [Marks 6]
(b) Suppose that 100 of the 120 mathematics students of the college take at least one of the language French, German and Russian.65 study French, 45 study German, 42 study Russian. Find the number of students who study all three languages.
Show the whole structure by Venn diagram. [Marks 6]
(c) Show the following sets by Venn diagram.
(i) (A-B)c (ii) Ac D B (iii) A DBDC [Marks 6]
Q. 2 Attempt any two
(a) There are 3 toys to be distributed among 7 children. In how many ways can it be done such that (i) No child gets more than one toy. (ii) There is no restriction as to the number of toys any child gets. (iii) No child gets all toys.
[Marks 6]
(b) In an examination a minimum is to be secured in each of 4 subjects to pass. In how many ways can a student fail? [Marks 6]
(c) A husband and wife appear in an interview for two vacancies in the same
1 1 post. The probability of husbands selection is - and that of wife's selection is -.
What is the probability that (i) both of them will be selected, (ii) Only one of them will be selected, (iii) None of them will be selected. [Marks 6]
Q. 3 Attempt any two
(a) Show that the relation x = y(mod 5) i.e. x-y is divisible by 5 defined on the set of integers I is an equivalence relation. [Marks 6]
(b) Show that the relation defined on the set of integers is partial order relation. [Marks 6]
(c) Draw Hasse diagrams of all lattices with up to five elements. [Marks 6] Q.4 Attempt any two
(a) For the graph G shown below, use Dijkstra's algorithm to compute the shortest path between the vertices 'a' and 'z'. [Marks 6]
 |
z |
(b) A connected planar graph has seven vertices having degrees 3, 3, 2, 3, 3, 2 and 4. How many edges are there? How many regions are there? Also draw one such graph. [Marks 6]
(c) State the travelling salesman problem and use it to find the shortest Hamiltonian cycle in the graph given below. [Marks 6]
Q.5 Attempt any two.
(a) Use Prim's algorithm to find the minimum spanning tree for the graph given below. [Marks 6]
(b) Construct a binary tree whose in-order and pre-order traversal is given below.
i. In-order : 5, 1, 3, 11, 6, 8, 2, 4, 7.
ii. Pre-order : 6, 1, 5, 11, 3, 4, 8, 7, 2. [Marks 6]
(c) Construct the binary tree for the expression y + x + 2 = (x * x) + y + (2 * x * y) + 3 * x * x * z
[Marks 6]
|
Attachment: |
| Earning: Approval pending. |
