Osmania University (OU) 2008 M.Sc Computer Science Discrete Mathematical Structure - Question Paper

Faculty of Science
M.Sc I-Semester exam Nov./Dec 2008
COMPUTER SCIENCE
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
Paper -- 1.1 (Discrete Mathematical Structure)
```````````````````````````````````````

part -- A (Marks : eight X four = 32)
************************************

1. Prove that ~(p^q) is equivalent to ~pv~q.
2. provided 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 lowest 2 vertices of degree one.
5. How many ways can we get a sum of four or of eight when 2 distinguishable dice are rolled?
6. How many thre-digits numbers are there which are even and have no repeated digits?
7. obtain 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.

part -- B (Marks : four 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 obtain 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 1st n+1 Fibonacci numbers is 1 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.

Earning:   Approval pending.