M.Sc (CS) I-Semester Examination Nov./Dec 2008, Discrete Mathematical Structure

Faculty of Science
M.Sc I-Semester Examination Nov./Dec 2008
COMPUTER SCIENCE

Paper -- 1.1 (Discrete Mathematical Structure)


SECTION -- A (Marks : 8 X 4 = 32)
************************************

1. Prove that ~(p^q) is equivalent to ~pv~q.
2. Given p, p->q and q --> r, prove r without using truth table.
3. In any graph, show that the sum of the degrees of vertices is twice the number of edges.
4. Show that every tree has at least two vertices of degree one.
5. How many ways can we get a sum of 4 or of 8 when two distinguishable dice are rolled?
6. How many thre-digits numbers are there which are even and have no repeated digits?
7. Find the coefficient of X^23 in (1+x^5+x^9)^10.
8. Solve the recurrence relation:

A(n)-7A(n-1)+10A(n-2) =0 for n>=2.

SECTION -- B (Marks : 4 X 12 = 48)
*************************************

9. (a) (i) Show that P <->q is equivalent to (P^q)v(~p^~q).
(ii) Show that syllogism is a valid rule of interface.

(OR)

(b) (i) Show that P^q is equivalent to (p NAND q) NAND (p NAND q).
(ii) Write the dual of the expression [(a+b)+(a+c)}ac1.

10. (a) (i) Show that in a connected plannar graph with e edges and v vertices , 3v-e >=6.
(ii) State and prove Euler's formula.

(OR)

(b) Use Dijkstra's algorithm to find the shortest path from A to Z.

(Graph Diagram is there...)

11. (a) (i) How many binary sequences are there of lenth 15?
(ii) How many integral solutions are there to X1+X2+X3+X4+X5 = 20 where X1>= 3, x2 >=2, X3>=4, x4>=6 and x5>=0?

(OR)

(b) Prove that the number of derangement of {1,2,3,......,n} is Dn = n![ 1-1/1!+1/2!+1/3!+....+(-1)^n/n!].

12 (a) (i) Show that the sum of the first n+1 Fibonacci numbers is one less than Fn+2.
(ii) Solve An-7An-1+10An-2 = 4^n for n >= 2.

(OR)

(b) (i) Solve An-An-1+9An-2+9An-3 = 0 for n>=3 and A0 =0, a1 = 1, a2 =2 using generating funtions.
(ii) Solve Sq.r(An)-Sq.r(An-1)-2Sq.rt(An-2) = 0 where A0 = A1 = 1.