Skip to content

Discrete Mathematics

CSE · Final · Summer 26

Paper 3 of 5Section 69-K · Batch 69Switch

Section 69-K · Batch 69

Paper 3 of 5

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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 * 3 + 2 * 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' with vertices v1, v2, v3, v4, v5 and w1, w2, w3, w4, w5, w6, w7 respectively] 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: A connected graph with labeled vertices s, t, u, v, w, x, y, z and 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] [CO3] [Figure: A weighted undirected graph with nodes A, B, C, D, E, F, G, H and weighted edges] 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 12 0 0 ) ( 20 0 0 0 0 8 ) ( 0 6 0 0 0 0 ) ( 0 0 0 0 0 0 )