NARULA INSTITUTE OF TECHNOLOGY
An Autonomous Institute under MAKAUT
B.TECH./CSE, CST, AIML/ODD/3RD SEM/ R_21/M(CSE)301/2022-2023
YEAR: 2022
DISCRETE MATHEMATICS
M(CSE)301
TIME ALLOTTED: 3 HOURS FULL MARKS: 70
The figures in the margin indicate full marks.
Candidates are required to give their answers in their own words as far as practicable
GROUP – A
(Multiple Choice Type Questions)
1. Answer any ten from the following, choosing the correct alternative of each question: 10×1=10
SL Question Marks Co Blooms
Taxonomy
Level
(i) A group is abelian iff 1 1 Understand
a) ab=ba
b) ab=ab
c) ba=ba
d) none
(ii) Which of the following set is closed under numerical 1 1 Understand
multiplication
a) {1, -1, 0, 2}
b) {1, i}
c) {1, ω, ω2}
d) {ω, 1}
(iii) The only generators of the cyclic group (Z, +) is 1 2 Understand
a) 1
b) 0, 1
c) 1, -1
d) All positive integers
(iv) A semi group (G, *) will be monoid if 1 1 Understand
a) * Is associative
b) * is commutative
c) G contains inverse of every element
d) G contains identity element
(v) An edge whose two end vertices coincide is called 1 1 Understand
a) ring
b) loop
c) adjacent edge
d) none
(vi) The degree of an isolated vertex is 1 1 Understand
a) 0
Odd semester theory examination 2022 under autonomy, 14th-DEC-22
Page 1 of 4
NARULA INSTITUTE OF TECHNOLOGY
An Autonomous Institute under MAKAUT
b) 1
c) 2
d) none
(vii) If a graph has 5 vertices and 7 edges then the size of the adjacency 1 1 Understand
matrix is
a) 5 5
b) 5 7
c) 7 5
d) 7 7.
(viii) A self-loop cannot be included in a 1 1 Understand
a) Walk
b) Path
c) Trail
d) None
(ix) The proposition p∧(~pvq) is 1 1 Understand
a) Tautology
b) Logical equivalence to p∧q
c) Logical equivalence to pvq
d) Contradiction
(x) is a contradiction 1 1 Understand
a) True
b) False
(xi) A Poset in which every pair of elements has both a least upper 1 1 Understand
bound and a greatest lower bound is termed as _______
a) sublattice
b) lattice
c) trail
d) walk
(xii) Which of the following statement is a proposition? 1 1 Understand
a) Get me a glass of milkshake
b) God bless you!
c) What is the time now?
d) The only odd prime number is 2
GROUP – B
(Short Answer Type Questions)
(Answer any three of the following) 3 x 5 = 15
SL Question Marks Co Blooms
Taxonomy
Level
2. (i) Show that a group is (G, o) abelian if and only if (a o b)2= a2 o b2, 3 3 Apply
∀ a, bϵ G
(ii) Let G be a group and H, K are subgroups of G .Then H K is a 2 3 Explain
subgroup of G.
3. Check whether ( p˄q)˅(q˄r)↔ (r˄p) is a tautology or not. 5 2 Apply
Odd semester theory examination 2022 under autonomy, 14th-DEC-22
Page 2 of 4
NARULA INSTITUTE OF TECHNOLOGY
An Autonomous Institute under MAKAUT
4. (i) Prove that if gcd(a,b)=1,then gcd(a2,b2)=1 2 2 Apply
(ii) Find the remainder when the sum 1!+2!+3!+4!+…..+100! is 3 1 Evaluate
divided by 30.
5. Draw Hasse diagrams of the posets (S,) for 5 1 Evaluate
S={2,4,5,6,10,12,20,25} where be a partial ordering relation
defined on S such that ab iff a divides b
6. State the rules of kruskal’s Algorithm. Obtain minimal spanning 5 4 Evaluate
tree of the following graph using Kruskal’s algorithm:
GROUP – C
(Long Answer Type Questions)
(Answer any three of the following) 3 x 15 = 45
SL Question Marks Co Blooms
Taxonomy
Level
7. (i) Solve the recurrence relation 8 1 Evaluate
(ii) Define regular graph. Draw the graph for the following incidence matrix 7 4 Evaluate
and explain
8. (i) Prove that every group of prime order is cyclic 5 3 Apply
(ii) a 0 5 3 Evaluate
Show that the set of matrices b 0 is a subring of the ring of 2x2
matrices over the field of real numbers.
(iii) Check whether (S, ≤) is a lattice or not where S={1,2,3,4,6,9,12,18,36} 5 1 Explain
Also find the supremum and infimum of the set {4,6,9} and {2,3}
Odd semester theory examination 2022 under autonomy, 14th-DEC-22
Page 3 of 4
NARULA INSTITUTE OF TECHNOLOGY
An Autonomous Institute under MAKAUT
9. (i) Among 100 students, 32 study mathematics, 20 study physics, 45 study 5 1 Evaluate
chemistry, 7 study mathematics and physics, 15 study mathematics and
chemistry, 10 study physics and chemistry, 30 do not study any of the
three subjects. Determine the number of students studying exactly one of
the three subjects.
(ii) Define complete graph. Construct the adjacency matrix for the following 6 4 Evaluate
di-graph and explain
(iii) Find the minimum number of students needed to guarantee that 5 of 4 1 Apply
them belong to same class (1st year, 2nd year, 3rd year and 4th year)
10. (i) Find the PDNF and PCNF of using truth table. 7 2 Evaluate
(ii) Apply Dijktra’s algorithm to find the out shortest path of the following 8 4 Apply
graph
11. (i) Calculate the gcd (1761, 189) and express it as 1761u+189v 6 2 Evaluate
(ii) Using generating function solve the recurrence relation: an-7an-1+10an- 9 1 Evaluate
2=2 for all n>1 with a0=a1=3
Odd semester theory examination 2022 under autonomy, 14th-DEC-22
Page 4 of 4
