MCA I (First) Semester Examination 2015-16
Course Code:MCA103 Paper ID: 0871203
Discrete Mathematics
Time: 3 Hours Max. Marks: 70 Max Marks: 75
Note: Attempt six questions in all. Q. No. 1 is compulsory.
1. Answer any five of the following (limit your answer to 50 words). (4x5=20)
a) Define a graph.
b) Define planar and draw K4 planar graph.
c) What do you understand by "Contradiction" in Propositional Calculus?
d) Prove that the number of permutations of n things taken all at a time is n!.
e) Define inorder, preorder and postorder tree traversal techniques.
f) What do you understand by valid arguments and fallacy arguments?
g) Define linear recurrence relations. Also differentiate between homogeneous and non-homogeneous recurrence relations.
h) State Eular theorem. Verify Eular’s formula for a map in figure 1.
Fig. 1
2. a) Is the proposition p ∨ ¬(p ∧ q) a tautology? (5)
b) Transform the following formula into Conjunctive Normal Form. Show intermediate steps
¬(p → q) ∨ (r → p). (5)
3. Use mathematical induction to prove that 12 + 22 + 32 + ... + n2 = n (n + 1) (2n + 1)/ 6 for all positive integers n. (10)
4. a) Explain travelling salesman problem. (5)
b) Explain Chinese Postman problem. (5)
5. a) Briefly explain Pigeon-Hole Principle. (4)
b) Show that if any four numbers from 1 to 6 are chosen, then two of them will add to 7. (6)
6. a) Consider the graph G where
V(G) = {A, B, C, D} and E(G) = {{A,B}, {B,C}, {B,D},{C,D}, {D,A}}.
Find the degree and parity of each vertex in G. (5)
b) Let G be the graph in Fig. 2. Determine whether or not each of the following sequences of edges form a path: (5)
i) {{A,X},{X,B},{C,Y},{Y,X}}
ii) {A,X},{X,Y},{Y,Z},{Z,A}}
iii) {{X,B},{B,Y},{Y,C}}
iv) {B,Y},{X,Y},{A,X}}
7. a) Explain Four Color theorem. (4)
b) Explain what is meant by a spanning tree and a minimal spanning tree. Find a spanning tree for a graph G shown in Fig. 2. (6)
Fig. 2
8. Solve the following recurrence relations using characteristic equations.
a) an = 5an-1 − 6an-2 with initial conditions a0 = 1 and a1 = 4
b) an = 6 an-1 − 9 an-2 with initial conditions a0 = 4 and a1 = 6.
(10)