Discrete Mathematics
CSE · Final · Summer 25
Paper 3 of 3By SAFIUL ISLAMSwitch
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 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]
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. [5] [CO3] [Figure: Graph G and Graph G']
b) Apply the concept of Dijkstra's algorithm to find the shortest path from Node 1 to Node 8. [5] [Figure: Weighted graph with nodes 1 to 8]
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. [4] [CO3] [Figure: Graph with vertices a, b, c, d, e, f]
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. [6] [Figure: Graph A and Graph B]
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. [7] [CO3] [Figure: Weighted graph with nodes A, B, C, D, E, F, G, H, J]
b) Draw Graph A from the following adjacency matrix. [3] [Figure: 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))]