First question is compulsory.

Answer any FOUR from the remaining questions.

All questions carry equal marks.

Answer all parts any question at one place.

(a)   If  A={1,2} and B={a,b} then write ρ (AXB) where ρ (AXB)denotes the power set of A X B.

(b)   Write the statement in predicate calculus:

There is a shop in wvery street.

(c)    How many three digit numbers can be formed from the digits 0,1,2,3,4?

(d)   Find the number of terms in the expansinon of (x+y+z)5.

(e)   Define binary tree.

(f)     Give an example of a digraph with four nodes each having in-degree 2.

(g)   Degfine partial ordering.

2. (a) Verify whether the folowing is a tautology or not.

((P->Q)->R)->((P->Q)->(P->R)).

(b) Using mathematical induction,prove that the product of any 3 consecutive integers is divisible by 6.

3.  (a) If A and B are two sets then define AB=(A-B)(B-A) with A={1,2,3} and B={1,3,5} then find the set ((AB)B)-(A(BB)).

(b) Ifρ(φ) denotes the power set of the empty set φ then write explicitly the elements of ρ(

4. (a) How many integral solutions are ther to x1+x2+x3+x4+x5+=20 where each xi>=2?

(b) Represent the relatin R={(1,2),(1,3),(2,3(3,1)} on the set A={ 1,2,3} as a digraph and find it’s transitive closure.

5. (a) If A is a non- empty finite set then prove that any function f:A->A is one-one if and only if it is onto.

(b) Show that the value of A(2,2)=7 where the A(m,n) is recursively fefined as follows:

A(0,n)=n+1

A(m,0)=A(m-1,1)if m>0

A(m,n)=A(m-1, A(m,n-1)) if m>0 and n>0.

6. (a) Prove that the sum of all the in-degree of the nodes of a graph is equal to the sum of all the out-degree of the nodes of al graph.

(b)  Check whether the following graphs are isomorphic or not ?

(GRAPH)

7.  (a) Find all solutions of the recurrence relation an = 5 an-1-6 an-2+7n.

(b) Writ e the Kruskal’s algorithm for finding the minimun spanning tree of a graph.

8.  (a) Define the reaversals of a binary tree and illustrate with an example.

(b) Construct the binary tree whose preorder sequence is A B C D E F G H I  and with the in-order sequnece is B C A E D G H F I.

IT 2.1 Previous PapersCSE,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 parts any question at one place.  Answer the following. (a)   If  A={1,2} and B={a,b} then write ρ (AXB) where ρ (AXB)denotes the power set of A X B. (b)   Write the statement in predicate calculus: There is a...