M.C.A. (Engg.) Direct 2nd Year Students (Bridge Course) Examination, 2018
Paper I DISCRETE MATHEMATICAL STRUCTURE
Day and Date Thursday, 20-12-2018 Total Marks 100
Time 10.30 a.m. to 1.30 p.m.
Instructions Draw diagram wherever necessary.
Figures to the right indicate full marks.
1. Choose the correct alternative 20
A is an ordered collection of objects.
Relation Function Set Proposition
6P4 is equal to
36 360 6 4
The set of positive integers is
Infinite Finite Subset Empty
A matrix having many rows and one column is known as
Row matrix Column matrix
Diagonal matrix None of the mentioned
The set O of odd positive integers less than 10 can be expressed by

11}
Power set of empty set has exactly subset.
One Two Zero Three
What is the cardinality of the set of odd positive integers less than 10
10 5 3 20
Which of the following two sets are equal
A and B
A and B
A and B
A and B
What is the Cardinality of the Power set of the set
8 6 7 9
10) The members of the set S x is the square of an integer and x 100} is
58, 49, 56, 99, 12}
16, 25, 36, 49, 64, 81}
16, 25, 36, 64, 81, 85, 99}
16, 25, 36, 49, 64, 121}
11) A symmetric matrix is a one in which
All diagonal elements are zero All diagonal elements are 1
A AT A -AT
12) A matrix having one row and many columns is known as
Row matrix Column matrix
Diagonal matrix None of the mentioned
13) If matrix A and B are symmetric and AB BA iff
AB is symmetric matrix
AB is an anti-symmetric matrix
AB is a null matrix
None of the mentioned
14) Trace of the matrix of odd ordered anti-symmetric matrix is
0 1
2 All of the mentioned
15) In how many ways can 5 balls be chosen so that 2 are red and 3 are black
910 990 980 970
16) Which of the following statement is true
Every graph is not its own sub graph.
The terminal vertex of a graph are of degree two.
A tree with n vertices has n edges.
A single vertex in graph G is a sub graph of G.
17) An arrangement of finite numbers of objects taken some or all at a time is
called their
A.P. Combination Sequence Permutation
18) In nC12 nC6 value of n is
12 14 16 18
19) 6P1 is equal to
18 12 6 0
20) The trace of the matrix is defined as
Sum of all the elements of the matrix
Sum of all the elements of leading diagonal of matrix
Sum of all non-zero elements of matrix
None of the mentioned
2. Write short note on (any 20
Explain POSET and Hasse diagram.
Explain C artesian product with an example.
Explain inorder and postorder.
Explain connected and disconnected graph.
Explain set operations.
3. What is relation Explain reflexive, irreflexive and transitive relation with an
example. 10
What is graph Explain walk, length of walk and closed walk with an
example. 10
OR
Explain travelling salesman problem with an example. 10
SECTION ii
4. Write short note on (any 20
Write in brief about regular Expression.
Explain in detail the characteristics of Automation.
Draw a state table for a NDFA given by the regular expression

Write short note on applications of Pumping Lemma for Regular Sets.
Explain in detail Moore machine.
5. Write long answer on Regular Sets and Regular Grammar with example. 10
Explain minimization of finite automata with example. 10
OR
Explain the conversion of N ondeterministic Systems to Deterministic
Systems. 10