First Question is compulsory

Answer any FOUR from the remaining questions

All questions carry equal marks

Answer ALL psarts of any question at one place

1. (a)  Show that if  A  and B are sets, then  A-B=AΠ~B.

(b) Use proof by contradiction to prove that “for every integer  n, if n2 is odd, then n is odd”.

(c) How many  4 digit numbers, not beginning with zero,without repeating an digit can be formed         using 0,1,2,3,4.

(d) Solve the rcurrnce relation an+1=4an for n>=0, given that a0=3.

(e) What are the in degrees of the vertices in the graph G displayed int the given figure?

(f) What is chromatic numbers?

(g) What is max number of vertices in the entire tree of height ‘h’ and degree ‘k’?

2. (a)  Prove the following

i.            [(p->q)->q] Ξ p ѵ q

ii.            [(p->r) ^ (q->r)]Ξ (p ѵ q) ->r

(b) Prove that 2n <n!  using mathematical induction.

3.    (a) Determine the integer solutions of x1+x2+x3+x4=32 where x1x2>=7.

(b) A new state flag is to be designed with six vertical strips in yellow,white, blue and red.

In how many ways can this be done so that number of two adjacent strips have the same      color.

4.    (a) Out of 30 students in a hotel 15 study history, 8 study economics and 6 study geography. It   is known that 3 students study all these subjects. Show that 7  or more students study none of these subjects.

(b) Solve the recurrence relation an+7an-1+8an-2=0 n>=2,a0=2,a1=-7.

5.   (a) If A={1,2,3,5,30} and R is divisibility relation prove that  (A,R) is a lattice but not a distri

Butive  lattice.

(b) Give the adyacency matrix of the diagraph G=({a,b,c,d},R) where R={(a,b),(b,c),(d,c),(d,a)}.

6.    (a) Let m  be a positive integer with m>1. Show that the relation  R={(a,b)/aΞb(mod m)} is an equivalence relation on the set of integers.

(b) Define chromatic number. Find chromatic number of cycle,path and complete bipartite graph.

7.     (a) write and explain Prim’s algorithm for finding  the minimum spanning trees.

(b) State and prove De-morgan’s laws in Boolean algebra.

8.      (a)  Using Karnaugh map representing fins the minimal sum of products expression of  f(a,b,c,d)=∑(0,1,2,3,13,15).

(b) write an algorothm for the post-order traversal of binary tree.

UncategorizedCSE,CSE Previous Papers,Discrete Mathematical Structures-I Previous Papers,IT,IT Previous Papers
First Question is compulsory Answer any FOUR from the remaining questions All questions carry equal marks Answer ALL psarts of any question at one place   (a)  Show that if  A  and B are sets, then  A-B=AΠ~B. (b) Use proof by contradiction to prove that “for every integer  n, if n2 is odd, then n...