Discrete Mathematics
CSE · Final · Fall 24
Paper 2 of 3Batch 65 · SUPAN ROYSwitch
Batch 65
Paper 2 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.
[4] [CO2]
1. 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.
[6] [CO2]
2. a) Prove whether the following graphs G and G' are isomorphic or not?
[Figure: Two graphs G and G' with vertices labeled, showing their connectivity structure]
[4] [CO3]
2. b) Apply the concept of Dijkstra's algorithm to find the shortest path from a to z.
[Figure: A weighted connected graph with vertices a, b, c, d, e, f, g, z and weighted edges between them]
[6] [CO3]
3. a) Justify whether the following graphs are bipartite or not.
[Figure: Two graphs labeled Graph: A and Graph: B with various vertices such as v1, v2, v3, etc.]
[7] [CO3]
3. b) Draw these Graphs-
i. C_5
ii. K_{4,3}
iii. W_7
[3] [CO3]
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 undirected graph with nodes a, b, c, d, e, f, g and edges with weights 1, 7, 4, 3, 2, 5, 6, 9, 10, 8]
[7] [CO3]
4. 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] [CO3]