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

*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 n^{2} 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 a_{n+1}=4a_{n }for n>=0, given that a_{0}=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 2^{n }<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 a_{n}+7a_{n-1}+8a_{n-2}=0 n>=2,a_{0}=2,a_{1}=-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.

http://www.stepinau.com/2013/09/26/andhra-university-beb-tech-discrete-mathematical-structures-i-previous-paper-2009/UncategorizedCSE,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.