Discrete Mathematics
CSE · Final · Fall 24
Paper 3 of 3Batch 65 · Lakshmi Kanta RoySwitch
Batch 65
Paper 3 of 3
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Faculty of Science & Information Technology
Department of Computer Science & Engineering
Final Semester Examination, Fall 2024
Course Code: CSE212, Course Title: Discrete Mathematics
Level: 2 Term: 1 Batch: 65
Time: 2:00 Hrs
Marks: 40
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.]
1. a) Determine whether the given relation is reflexive, symmetric, transitive, or none of these. Justify your answers.
i. C is the circle relation on the set of real numbers: For every x, y in R, x C y <=> x^2 + y^2 = 1.
ii. D is the "divides" relation on Z+: For all positive integers m and n, m D n <=> m | n
[CO2] [4]
b) Use mathematical induction to prove that for all non-negative integers n:
1 + 1/2 + 1/2^2 + 1/2^3 + ... + 1/2^n = 2 - 1/2^n
[CO3] [6]
2. a) Prove whether the following graphs G and G' are isomorphic or not?
[Figure: Two graphs G and G' with vertices labeled a, b, c, d, e, f, g, h and corresponding primed vertices]
[CO3] [4]
b) Apply the concept of Dijkstra's algorithm to find the shortest path from a to z.
[Figure: A weighted undirected graph with nodes a, b, c, d, e, f, g, z and weighted edges]
[CO3] [6]
3. a) Justify whether the following graphs are bipartite or not.
[Figure: Two graphs labeled Graph: A and Graph: B with vertices v1, v2, v3, etc.]
[CO3] [7]
b) Draw these Graphs:
i. C5
ii. K4,3
iii. W7
[3]
4. a) Apply Prim's algorithm on the following graph starting at node a to construct a minimum spanning tree indicating the order in which edges are added to form each tree, and find the weight of the tree.
[Figure: A weighted graph with nodes a, b, c, d, e, f, g and weighted edges]
[CO3] [7]
b) Draw a graph from the following adjacency matrix.
[[0, 0, 0, 1, 2], [0, 0, 0, 1, 1], [0, 0, 0, 2, 1], [1, 1, 2, 0, 0], [2, 1, 1, 0, 0]]
[3]