# Andhra University BE/B.Tech Discrete Mathematical Structures-I Previous Paper 2008

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 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 x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+=20 where each x_{i}>=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 a_{n }= 5 a_{n-1}-6 a_{n-2}+7^{n}.

(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.

http://www.stepinau.com/2013/09/26/590/IT 2.1 Previous PapersCSE,CSE Previous Papers,Discrete Mathematical Structures-I Previous Papers,IT,IT Previous Papers
## Leave a Reply

You must be logged in to post a comment.