Discrete Mathematics
CSE · Final · Fall 24
Paper 1 of 3Batch 65 · MD. MUSHFIQUL ISLAM 2.4231E+14Switch
Batch 65
Paper 1 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. [4]
i. C is the circle relation on the set of real numbers: For every x, y ∈ 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]
1. b) Use mathematical induction to prove that for all non-negative integers n, [6]
1 + 1/2 + 1/2^2 + 1/2^3 + ... + 1/2^n = 2 - 1/2^n
2. a) Prove whether the following graphs G and G' are isomorphic or not? [4]
[Figure: Two graphs G and G' with vertices labeled, where G has vertices a, b, c, d, e, f, g, h and G' has vertices s, t, u, v, w, x, y, z]
[CO3]
2. b) Apply the concept of Dijkstra's algorithm to find the shortest path from a to z. [6]
[Figure: A weighted connected graph with vertices a, b, c, d, e, f, g, z and edge weights 1, 4, 7, 8, 2, 5, 20]
3. a) Justify whether the following graphs are bipartite or not. [7]
[Figure: Graph A with vertices v1, v2, v3, v4, v5, v6 and Graph B with vertices v1, v2, v3, v4, v5, v6, v7]
[CO3]
3. b) Draw these Graphs- [3]
i. C5
ii. K4,3
iii. W7
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. [7]
[Figure: A weighted connected graph with vertices a, b, c, d, e, f, g and edge weights 1, 8, 10, 9, 7, 4, 3, 2, 5, 6]
[CO3]
4. b) Draw a graph from the following adjacency matrix. [3]
[ 0 0 0 1 2 ]
[ 0 0 0 0 1 ]
[ 0 0 0 2 1 ]
[ 1 1 2 0 0 ]
[ 2 1 1 0 0 ]