Discrete Mathematics
CSE · Final · Summer 26
Paper 2 of 5Batch 69 · Md. Oliul Islam BappySwitch
Batch 69
Paper 2 of 5
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 2026
Course Code: CSE212, Course Title: Discrete Mathematics
Level: 2 Term: 1 Batch: 69
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) Let P be the set of all real numbers, R. Define a relation Q on P such that for all x, y ∈ R, xQy if and only if x - y is an integer (i.e., x - y ∈ Z). Determine whether or not the relation Q is: (a) Reflexive (b) Symmetric (c) Antisymmetric (d) Transitive. Justify your answers. [4]
b) Use mathematical induction to establish the following identity for any positive integer n:
1 * 2 + 2 * 3 + 3 * 4 + ... + n(n + 1)(n + 2) = n(n + 1)(n + 2)(n + 3) / 4 [6] [CO2]
2. a) Prove whether the following graphs G and G' are Isomorphic or not. [5]
[Figure: Two graphs G and G']
b) Consider a tech startup with 10 employees, consisting of exactly 6 Software Engineers and 4 Quality Assurance (QA) Testers, who are setting up a strict cross-department peer-review network. Under their new rules, Software Engineers cannot review other Software Engineers' code, and QA Testers cannot review other QA Testers' code. Furthermore, each Software Engineer must have their code reviewed by exactly 2 different QA Testers, while each QA Tester is required to review the code of exactly 3 different Software Engineers to ensure a perfectly balanced workload. Is it possible to model this peer-review network using a graph? If it is possible, draw the graph. If you think it is not possible, explain why it cannot be modeled. [5] [CO3]
3. a) Find out if the graph below is Eulerian. If so, write the sequence of vertices of a Eulerian circuit. If not, explain why it isn't Eulerian. [4]
[Figure: An undirected graph with vertices u, v, w, x, y, z and multiple edges]
b) Due to severe monsoon flooding in the Chattogram division, a rapid response medical convoy needs to map out the most efficient delivery route to different regional hubs across Bangladesh. You have been provided with the accessible road network data, where the cities represent nodes and the two-way roads represent undirected edges. The current travel times between the connected cities are given in hours.
The Road Network Data:
Node | Regional Hub | Connecting Roads & Travel Times (hours)
D | Dhaka | N (2), B (4), M (2)
N | Narsingdi | D (2), C (5)
M | Munshiganj | D (2), B (1)
B | Brahmanbaria | D (4), M (1), C (2), S (6)
C | Cumilla | N (5), B (2), F (4), H (2)
S | Sonaimuri | B (6), H (1), T (6)
H | Hajiganj | C (2), S (1), K (5)
F | Feni | C (4), K (2), T (7)
K | Khagrachari | H (5), F (2), T (2)
T | Teknaf | S (6), F (7), K (2)
Now, apply the shortest path algorithm to find the shortest path from Dhaka to the Teknaf regional hub along with the travel time in hours. [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 total weight of the tree. [7]
[Figure: A weighted undirected graph with vertices A, B, C, D, E, F, G, H]
b) Draw the graph G that is represented by the following weighted adjacency matrix A. [3]
A = [
[0, 10, 0, 0, 5, 0],
[0, 0, 15, 0, 0, 0],
[0, 0, 7, 2, 0, 0],
[20, 0, 0, 9, 8, 0],
[0, 6, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]
]