Code: A-20

Code: C-10 Subject: DISCRETE STRUCTURES

Time: 3 Hours Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1 Choose the correct or best alternative in the following: (2x10)

a. Which of the following statement is the negation of the statement “2 is even or –3 is negative”?

(A) 2 is even & -3 is negative (B) 2 is odd & -3 is not negative

(C) 2 is odd or –3 is not negative (D) 2 is even or –3 is not negative

b. The statement ( pÙq) Þ p is a

(A) Contingency. (B) Absurdity

(C) Tautology (D) None of the above

c. In how many ways can a president and vice president be chosen from a set of 30 candidates?

(A) 820 (B) 850

(C) 880 (D) 870

d. The relation { (1,2), (1,3), (3,1), (1,1), (3,3), (3,2), (1,4), (4,2), (3,4)} is

(A) Reflexive. (B) Transitive.

(C) Symmetric. (D) Asymmetric.

e. Let L be a lattice. Then for every a and b in L which one of the following is correct?

(A) (B)

(C) (D)

f. The expression is equivalent to

(A) (B) a+c

(C) c (D) 1

g. A partial order relation is reflexive, antisymmetric and

(A) Transitive. (B) Symmetric.

(C) Bisymmetric. (D) Asymmetric.

h. If n is an integer and n² is odd ,then n is:

(A) even. (B) odd.

(C) even or odd. (D) prime.

i. In how many ways can 5 balls be chosen so that 2 are red and 3 are black

(A) 910. (B) 990.

(C) 980. (D) 970.

j. A tree with n vertices has _____ edges

(A) n (B) n+1

(C) n-2 (D) n-1

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2 a. If A and B are two subsets of a universal set then prove that A-B= AÇ. (8)

b. In a class of 60 boys, 45 boys play cards and 30 boys play carrom. How many boys play both games? How many play cards only and how many play carrom only? (8)

Q.3 a. How many words can be obtained by arranging the letters of the word ‘UNIVERSAL’ in different way? In how many of them

(i) E,R,S occur together

(ii) No two of the letters E,R,S occur together. (10)

b. Define symmetric, asymmetric and antisymmetric relations. (6)

Q.4 a. Prove by mathematical induction that if a set A has n elements, then P(A) has 2ⁿelements. (8)

b. Let L be a lattice then for every a and b in L

if and only if a<=b (8)

Q.5 a. Using Boolean algebra show that

abc + + + = ab + ac + bc (8)

b. Explain extended pigeonhole principle and show that if 7 colors are used to paint 50 bicycles , at least 8 bicycles will be the same color. (4, 4)

Q.6 a. If a graph G has more than two vertices of odd degree, then prove that there can be no Euler path in G. (8)

b. Show that

ù ( P Q) ® (ù P (ù P Q ) Û (ù P Q) (8)

Q.7 What is minimum spanning tree of a graph? Write down Prim’s and Kruskal’s algorithms and execute them by taking a suitable example. (2,7,7)

Q.8 a. What is grammar? Define different types of grammars. (8)

b. Prove that the Digraph of a partial order has no cycle of length greater than 1. (8)

Q.9 a. How do you traverse a Binary Tree? Explain Preorder, Inorder and Postorder traversals with example. (10)

b. Consider the finite state machine whose state transsion table is :

	a	b
S0	S0	S1
S1	S1	S2
S2	S2	S3
S3	S3	S0

Draw the graph for it. (6)

Code: C-10 Subject: DISCRETE STRUCTURES

Time: 3 Hours Max. Marks: 100

S1