# Andhra University BE/B.Tech Discrete Mathematics Structures-II Previous Paper 2009

- (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 a_{n}-6a_{n-1}+8a_{n-2}=n4^{n} where a_{0}=8 and a_{1}=28.

(b) write a generating function for a_{r} where a_{r} 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}=a^{n}*b^{n}.

(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 k^{1} 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 A_{I} 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.

http://www.stepinau.com/2013/10/31/andhra-university-beb-tech-discrete-mathematics-structures-ii-2009/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
## Leave a Reply

You must be logged in to post a comment.