Discrete Mathematics
CSE · Final · Summer 25
Paper 2 of 3By MD. ABDUR RAFISwitch
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 Examination, Summer 2025
Course Code: CSE212, Course Title: Discrete Mathematics
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 relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x, y) ∈ R if and only if xy ≥ 0. Justify your answers.
[4]
1. b) By using mathematical induction prove that the given equation is true for all positive integers.
1 x 2 + 3 x 4 + 5 x 6 + .... + (2n - 1) x 2n = n(n+1)(4n-1)/3
[6] [CO2]
2. a) Prove whether the following graphs G and G' are Isomorphic or not.
[Figure: Graph G showing vertices A, B, C, D, E, F, G and Graph G' showing vertices 1, 2, 3, 4, 5, 6, 7]
[5] [CO3]
2. b) Apply the concept of Dijkstra's algorithm to find the shortest path from Node 1 to Node 8.
[Figure: A weighted undirected graph with nodes 1, 2, 3, 4, 5, 6, 7, 8 and various edge weights]
[5]
3. a) Find out if the graph below is Eulerian or Hamiltonian or both. If so, write the sequence of vertices of an Eulerian circuit and/or Hamiltonian cycle. If not, explain why it isn't Eulerian or Hamiltonian.
[Figure: A graph with vertices a, b, c, d, e, f and edges connecting them]
[4] [CO3]
3. b) Justify whether each of the following graphs are Bipartite or not. If Bipartite, redraw the graph identifying the partite sets. If not, explain why they are not Bipartite.
[Figure: Graph A with vertices a, b, c, d, e, f, g, h, i, j and Graph B with vertices r, s, t, u, v, w, x, y, z]
[6] [CO3]
4. a) Apply Prim's algorithm on the following graph starting at Node A to construct a Minimum Spanning Tree (MST) indicating the order in which edges are added to form the tree. and find the weight of the tree.
[Figure: A weighted undirected graph with nodes A, B, C, D, E, F, G, H, J and edge weights]
[7] [CO3]
4. b) Draw Graph A from the following adjacency matrix.
A =
[ [0, 2, 3, 0, 0],
[2, 0, 15, 2, 0],
[3, 15, 0, 0, 13],
[0, 2, 0, 0, 9],
[0, 0, 13, 9, 0] ]
[3]