GOVERNMENT COLLEGE OF ENGINEERING & CERAMIC TECHNOLOGY
AN AUTONOMOUS INSTITUTE
AFFILIATED TO MAKAUT (FORMERLY KNOWN AS WBUT)
Theory / B.Tech/CSE/IT/ SEM -IV/Semester End Examination/Paper Code- BS(CS/IT) 408/2023-24
Paper Name: Discrete Mathematics
Full Marks: 75 Time Allotted: 3Hours
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
[MCQ Type Questions][Compulsory]
1. Choose the correct alternatives of the following questions. Answer all questions.10 × 1 = 10
Marks CO
i) The unit digit in 7 is 1 1
a) 1 c) 3
b) 2 d) 4
ii) Every integer is of the form 1 1
a) 2k±1,2k±3 c) 3k,3k±1,3k±2
b) 4k+1,4k+3,4k+5 d) None of these
iii) Let G be a group and and 𝑎 ∈ 𝐺. If O(a)=20 ,then 𝑂(𝑎 ) = 1 4
a) 15 c) 12
b) 5 d) 20
iv) Which of the following statement is true 1 4
a) A semi group with an identity element is c) (Q,+) is a cyclic group.
called a monoid.
b) A groupoid is said to be a semi group,if the d) Identity element in a group is not unique.
binary operation is commutative.
v) The truth table for ~𝑃𝛬(𝑃 → 𝑄) has the outcomes: 1 3
a) F,T,F,T c) T,T,F,F
b) F,F,T,T d) T,F,F,T
vi) 𝑃𝑉(𝑄 ∧ 𝑅) ≡ (𝑃 ∧ 𝑅)𝑉(𝑃 ∧ 𝑄) This property is known as: 1 3
a) Distributive law c) De Morgan’s Law
b) Associative Law d) Identity property
vii) The solution of the recurrence relation 𝑎 = 2𝑎 + 1 with 𝑎 = 0 is 1 2
a) 1−2 c) 2 −2
b) 2 −1 d) 2 −1
viii) In a tree with 𝑛 vertices, how many edges are there? 1 5
a) 𝑛 c) 𝑛−2
BS(CS/IT) 408 DISCRETE MATHEMATICS CSE/IT SEM IV Page 1 of 3
b) 𝑛−1 d) 𝑛+1
ix) If a graph has 5 vertices and 3 edges then the Adjacent Matrix has the number of 1 5
elements as:
a) 15 c) 25
b) 9 d) 8
x) The generating function for the sequence {0,1,2,3,4,…} is 1 2
a) 𝑥 c) 𝑥
1−𝑥 1−𝑥
b) 𝑥 d) 𝑥
(1 − 𝑥) (1 − 𝑥)
GROUP – B
[Short Answer Type Questions]
Answer any FOUR of the following 4×5=20
Questions (2) to (7) Marks CO
2. Prove that a group (G,∘) is abelian if and only if (𝑎 ∘ 𝑏) = 𝑎 ∘ 𝑏 . 5 4
3. i) Describe all permuation on the set {1,2,3}.Find their respective orders. 3+2 4
ii)Determine whether the permutation 1 2 3 4 5 6 on the set {1,2,3,4,5,6}
2 3 5 6 1 4
is even or odd. Hence find it’s inverse
4. Solve the linear congruence 9𝑥 ≡ 21(𝑚𝑜𝑑 30). 5 1
5. Find all the Cliques and the Clique numbers of the graph 5 5
6. i. Express the graph as Bipartite and write both the sets of vertices with their elements. 5 5
ii. Define Planar Graph with an example.
7. Prove that (𝑝 ∧ (𝑝 → 𝑞)) → 𝑞 is a tautology with a truth table. 5 3
GROUP – C
[Long Answer Type Questions]
Answer any THREE of the following 3×15=45
Questions (8) to (12) Marks CO
8. a) Find integers 𝑢 and 𝑣 satisfying gcd(272,119) = 272𝑢 + 119𝑣. 5+4+4+2 1
b) If 𝑔𝑐𝑑(𝑎, 𝑏) = 1, prove that 𝑔𝑐𝑑
𝑔𝑐𝑑(𝑎 + 𝑏, 𝑎 − 𝑎𝑏 + 𝑏 ) = 1 𝑜𝑟 3.
c) Find the remainder when the sum 1! + 2! + 3! + ⋯ + 500! is divided by 12.
d) Show that 2 + 1 is divisible by 3 if 𝑛 is odd.
BS(CS/IT) 408 DISCRETE MATHEMATICS CSE/IT SEM IIV Page 2 of 3
9. a)Solve the recurrence relation 𝑎 − 7𝑎 + 10𝑎 = 2, ∀𝑛 ≥ 1, 𝑎 = 3, 𝑎 = 3. 5+5+5 2
b) Using Characteristic root method solve the recurrence 𝑎 − 6𝑎 + 8𝑎 =3 .
c) Find the generating function for the sequence {𝑛(7 + 2𝑛)}.
10. a) Show that all the roots of the equation 𝑥 = 1 forms a cyclic group under the 5+4+3+3 4
operation multiplication.
b) Define centre,Z(G) of a group G. Show that Z(G) is a subgroup of G.
c) In a group if every element is of order 2, then prove that the group is commutative.
d)Show that (Q,∙) does not form a group.
11. a) Draw the Dual of the graph where 𝑒 ′𝑠 are denoting edges, 𝑣 ′𝑠 are vertices. 3+6+4+2 5
b) Draw the minimum spanning tree of the graph
c) Find the Chromatic Number of the graph:
d) What is the Chromatic number of 𝐾 ? Explain.
12. a) Without Truth Table, show thatthat.~𝑝 ∧ (𝑝 ∨ 𝑞) ≡∼ 𝑝 ∧ 𝑞. Mention all the laws used 5+2+3+5 3
in each step.
b)(i) Mention if the following statement is Conjunction/Disjunction/ Negation and
convert it to a compound statement by using 𝑝 and 𝑞 for the simple statements and
write the propositional equivalence used.
(ii).Write
Write the Converse, Inverse and Contrapositive of the complex statement by
mentioning the required propositions as 𝑝 and 𝑞 and their operations in each case. “ I
take the medicine or I’ll be sick”
c) Generate the truth table for ∼ (𝑝 ∨∼ 𝑞) ∨∼ 𝑟 including the columns of each
operation one by one.
BS(CS/IT) 408 DISCRETE MATHEMATICS CSE/IT SEM IIV Page 3 of 3
