Code: AC10 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. If R is a
relation “Less Than” from A = {1,2,3,4} to B = {1,3,5} then RoR-1 is
(A) {(3,3),
(3,4), (3,5)}
(B) {(3,1), (5,1), (3,2), (5,2), (5,3), (5,4)}
(C) {(3,3),
(3,5), (5,3), (5,5)}
(D) {(1,3), (1,5), (2,3), (2,5), (3,5), (4,5)}
b. How many
different words can be formed out of the letters of the word
(A) 64 (B) 120
(C) 40320 (D)
720
c. Which of the
following statement is the negation of the statement “4 is even or -5 is
negative”?
(A) 4
is odd and -5 is not negative (B) 4
is even or -5 is not negative
(C) 4
is odd or -5 is not negative (D) 4
is even and -5 is not negative
d. A complete graph of n vertices should have
__________ edges.
(A) n-1 (B) n
(C) n(n-1)/2 (D) n(n+1)/2
e. Which one is the contrapositive of
?
(A) 
(B) 
(C) 
(D) None
of these
f. A relation that is reflexive, anti-symmetric
and transitive is a
(A) function (B) equivalence
relation
(C) partial
order (D) None
of these
g. A Euler graph is one in which
(A) Only
two vertices are of odd degree and rests are even
(B) Only two vertices are of even degree and rests are odd
(C) All
the vertices are of odd degree
(D) All the vertices are of even degree
h. What kind of strings is rejected by the
following automaton?
(A) All
strings with two consecutive zeros
(B) All
strings with two consecutive ones
(C) All
strings with alternate 1 and 0
(D) None
i. A spanning tree of a graph is one that
includes
(A) All
the vertices of the graph
(B) All the edges of the graph
(C) Only
the vertices of odd degree
(D) Only the vertices of even degree
j. The Boolean
expression 
is independent to
(A) A (B) B
(C) Both
A and B (D) None
Answer any FIVE Questions out
of EIGHT Questions.
Each question carries 16
marks.
Q.2 a. Write
the negation of each of the following in good English sentence.
(i) Jack
did not eat fat, but he did eat broccoli.
(ii) The
weather is bad and I will not go to work.
(iii) Mary
lost her lamb or the wolf ate the lamb.
(iv) I will
not win the game or I will not enter the contest. (2
x 4)
b. Simplify the logical expression 
. (8)
Q.3 a. How
many different sub-committees can be formed each containing three women from an
available set of 20 women and four men from an available set of 30 men? (8)
b. A box contains six red balls and four green
balls. Four balls are selected at random from the box. What is the probability
that two of the selected balls will be red and two will be green? (8)
Q.4 a. What
is a partition on a set? Let A = {1,2,3,4,5} and a relation R defined on A is
R={(1,1), (1,2), (2,1), (2,2), (3,3), (4,4), (4,5), (5,4), (5,5)}. Obtain the
cells of the partition. (8)
b. What
is a lattice? Which of the following graphs are lattice and why? (8)
(a)
(b)
(c)
Q.5 a. In
a survey of 85 people it is found that 31 like to drink milk 43 like coffee and
39 like tea. Also 13 like both milk and
tea, 15 like milk and coffee, 20 like tea and coffee and 12 like none of the
three drinks. Find the number of people
who like all the three drinks. Display
the answer using Venn Diagram. (8)
b. Obtain the incidence and the adjacency matrix
of the graph given below. (8)
Q.6 a. What
are the possible ways to combine two automatons? Explain with an example. (8)
b. Construct the finite automaton for the state
transition table given below. (8)
a b
start s0 s0 s2
s1 s0 s1
s2* s2 s1
Q.7 a. Prove
that if 
has a least element, then has a unique least element. (8)
b.
Show that in a Boolean algebra, for any a and b, (a Λ b) V (a Λ b' ) = a. (8)
Q.8 a. For the given graph,
find the minimal spanning tree using Prim’s algorithm. (8)
D
b. Show that is 
and 
are equivalence relations on A, then 
is an equivalence
relation. (8)
Q.9 a. Write
the Preorder, Inorder and Postorder tree traversal algorithm. (8)
b. Write down the
steps of the Warshall’s algorithm. (8)