1. (a)  Define the transitive closure of a binary relation.

(b)  Show that the sets of connective {V, }  and  {V,  }are functionally complete.

(c)   In howmany ways can a person climb up a flight of  n  steps if the person can skip atmost  One step at a time?

(d)  Draw the binary tree whose level order indices are {1,2,4,5,8,10,11,12}.

(e)  Compare Euler Circuit and Hamilton cycle.

(f)  State and prove the sum of degrees theorem.

(g)  What is monoid homomorphism?

2.(a) Obtain principal conjunctive normal form of yhe formula S given by

(   P→R)^(Q↔P)

(b) Show that R^9pvq) is a valid conclusion from the premises PVQ,Q→R and  M.

3.(a)  In how many ways van the letters {5c,4b,3c} be arranged so that all the letters of the same kind

Are not in a single block.

(b)  How many ways are there to distribuye 10 balls into 6 numbered boxes with batmost 4 balls in

The first 2 boxes (that is if X1=The number of balls in box I, then X1+X2<=4) if the balls are

Distinguishable.

4.(a)  Solve the recurrence relation an-6an-1+8an-2=n4n where a0=8 and a1=28.

(b)  write a generating function for ar where  ar  is the number of integers between 0 and 999 whose

Sum of digits is r.also find out the number of ways the sum  r can be obtained  when 2

Distinguishable dice are tossexd and the first shows an even number and the second shoes an

Odd number.

5.(a)  If  <G,*> is a abelian group thwn for all a,b £G  show that (a*b)n=an*bn.

(b)  let the alphabet  v={a,b} and A be the set including,the null string  ^,of all sequences   on  v

Beginning with a.show that <A,0,^> is a monoid where 0 is the concentration operation on strings.

6. (a)  W hat is graph isomorphism? When two graphs are said to be isomorphic? Explain wiyh example?

(b)   Prove that there are between 0 and k1 vertices at level l in any directed tree of degree k.

7. (a)  Use the principle of inclusion aid exclusion to count the no .of primes between 41 and 100.

(b)  Suppose that a set S has  n distinct elements.how many n-part ordered partitions(A1,A2,……An) are there in which each set AI has exactly one element?

8.Write short notes on the following

(a) Deterministic finite state machine.

(b) Hamming code.

(c) Krushals algorithm for finding optimal spanning tree.

CSE 2.2 SyllabusCSE,CSE 2.2 Previous Papers,CSE Previous Papers,Discrete Mathematics Structures-II Previous Papers,IT,IT 2.2 Previous Papers,IT Previous Papers
(a)  Define the transitive closure of a binary relation. (b)  Show that the sets of connective {V, }  and  {V,  }are functionally complete. (c)   In howmany ways can a person climb up a flight of  n  steps if the person can skip atmost  One step at a time? (d)  Draw the binary tree...