UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2024 Examination

GTU 3140708 Discrete Mathematics (DM) Winter 2024 Paper Solution & PDF

B.E. · Computer Engineering · Semester 4 · Subject Code: 3140708
Download Official GTU PDF
Share:
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Define onto function. Check whether the function 𝑓: ℝ → ℝ
defined by 𝑓(𝑥) = 𝑥2 is one-one and onto.
3 Marks
(b)
For the relation R = {(1,
1), (1,
2), (2,
1), (2,
2), (3,
3), (4,4)} on the set 𝐴 = {1,2,3,4}. Check whether it is reflexive, symmetric, anti-symmetric, transitive.
4 Marks
(c)
(
i)A history class contains 8 male students and 6 female students. Find the number 𝑛 of ways that the class can elect: (a) 1 class representative (b) 2 class representatives, 1 male and 1 female (c) 1 president and 1 vice president.
ii)Define elementary cycle, loop, tree and pendent vertex.3 Marks
7 Marks

Question 2

14 MarksMedium
(a)

Show that if every element in a group is its own inverse, then the group must be abelian.

3 Marks
(b)
Identify the statement (𝑝 → 𝑞) ⇆ (¬𝑝⋁𝑞) is tautology or
contradiction.
4 Marks
(c)
Use a truth table to determine whether the following argument form
is valid.
𝑝 → 𝑞
𝑞 → 𝑟
∴ 𝑝 → 𝑟
7 Marks
OR OPTION
(c)
(
i)Symbolize the following expressions “𝑥 is the father of the mother of 𝑦” where 𝑃(𝑥): 𝑥 is a person. 𝐹(𝑥, 𝑦): 𝑥 is the father of 𝑦. 𝑀(𝑥, 𝑦): 𝑥 is the mother of 𝑦.
ii)Show that the premises “Everyone in this discrete mathematics class has taken a course in computer science” and “Marla is a student in this class” imply the conclusion “Marla has taken a course in computer science.”3 Marks
3 Marks

Question 3

14 MarksMedium
(a)
Define homomorphism. Let 𝐺 be the group of real numbers under
addition, and let 𝐺′ be the group of positive real numbers under
multiplication. Check whether the mapping 𝑓 ∶ 𝐺 → 𝐺′ defined by
𝑓(𝑎) = 2𝑎 is a homomorphism.
3 Marks
(b)

Suppose that 100 mathematics students at a college taking at least one of the languages French, German, and Russian, given the following data: 65 study French, 45 study German, 42 study Russian, 20 study French and German, 25 study French and Russian, 15 study German and Russian.

1)Find the number of students who study all the three languages.
2)Find the number of students who study only French.
4 Marks
(c)
(
i)The subset 𝐻 = {0, 2} is a subgroup of (ℤ4, +4). Is 𝐻 a normal subgroup?
ii)Let ℤ𝑚 denotes the integers modulo 𝑚. Check whether ℤ𝑚 is a group under addition. If so, is it abelian group?3 Marks
7 Marks
OR OPTION
(a)
Find all the generators of cyclic group (ℤ5, +5).
3 Marks
(b)
Prove that 𝐴 ∩ 𝐵̅ = 𝐴 ∩ 𝐶̅ if and only if 𝐴 ∩ 𝐵 = 𝐴 ∩ 𝐶.
4 Marks
(c)

Consider the ring ℤ30 = {0, 1, 2, … ,29} of integers modulo 30.

aFind −8 and −17.
bFind 11−1, 13−1 and 14−1.
cLet 𝑓 (𝑥) = 2 𝑥 + 4. Find the roots of 𝑓(𝑥) over ℤ30.
7 Marks

Question 4

14 MarksMedium
(a)

Let 𝐴 = {1, 2, 3, 4} and the relation 𝑅 = {(1,

1), (1,
4), (4,
1), (4,
4), (2,
2), (2,
3), (3,
2), (3,
3)} on 𝐴. Write the matrix of 𝑅 and check whether the relation is an equivalence.
3 Marks
(b)

Let 𝑋 = {2, 3, 6, 12, 24, 36} and the relation ≤ be such that 𝑥 ≤ 𝑦 if 𝑥 divides 𝑦. Find

i)Lower bound of {3,6},
ii)Upper bound of {3,6},
iii)GLB of {3,6}, if exist,
iv)LUB of {3,6}, if exist.
4 Marks
(c)

Solve the recurrence relation using the method of generating function 𝑎𝑛 − 5 𝑎𝑛−1 + 6𝑎𝑛−2 = 3𝑛, 𝑛 ≥ 2, 𝑎0 = 0, 𝑎1 = 2.

7 Marks
OR OPTION
(a)
Let the relation 𝑅 = {(1,
2), (2,
3), (3,
3)} on 𝐴 = {1, 2, 3}. Find the transitive closure of 𝑅.
3 Marks
(b)
Solve 𝑎𝑛 = 2 𝑎𝑛−1 + 3𝑎𝑛−2, 𝑎0 = 1, 𝑎1 = 2.
4 Marks
(c)

Draw Hasse diagram of 〈𝑆30, 𝐷〉. Prove that 〈𝑆30, 𝐷〉 is a lattice, where 𝐷 is the relation of “division” in ℕ such that for any 𝑎, 𝑏 ∈ ℕ, 𝑎𝐷𝑏 if and only if 𝑎 divides 𝑏 and 𝑆𝑛, (𝑛 ∈ ℕ) is the set of all divisors of 𝑛.

7 Marks

Question 5

14 MarksMedium
(a)
Find the number of edges in a 𝑟-regular graph with 𝑛 vertices.
3 Marks
(b)
Check whether the following graphs are isomorphic or not.
4 Marks
(c)

In which order does a pre-order, in-order and post-order traversal visit the vertices of the ordered rooted tree shown in figure?

GTU Discrete Mathematics (3140708) Winter 2024 Question 5(c) Diagram
7 Marks
OR OPTION
(a)

A tree 𝑇 has 4 vertices of degree 2, 3 vertices of degree 3, 1 vertex of degree 4. Find the number of pendant vertices in the tree 𝑇.

3 Marks
(b)
Find reachable set of each node of the given digraph.
4 Marks
(c)

Define adjacency matrix. Use Warshall's algorithm to obtain path matrix from the adjacency matrix of

7 Marks
College Exam Groups

Studying for Discrete Mathematics?

Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.

Related papers

About this Examination Paper & Attribution

Official Gujarat Technological University (GTU) examination paper and step-by-step solutions for Discrete Mathematics (DM) (Winter 2024, B.E. · Computer Engineering, Sem 4). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.

Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.

Download PDF