Skip to content

Discrete Mathematics

CSE · Final · Spring 26

Batch 68

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, Spring 2026 Course Code: CSE212, Course Title: Discrete Mathematics Level: 2, Term: 1 Batch: 68 Time: 02: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) Consider the following relation on the set A={1,2,3,4,5,6}: R={(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6)} Determine whether or not the relation R on A is: (a) reflexive (b) symmetric (c) antisymmetric (d) transitive. Justify your answers. [4] [CO2] b) Use mathematical induction to prove that the following equation holds for all nonnegative integers n. 1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = ((n + 1)(2n + 1)(2n + 3)) / 3 [6] 2. a) Prove whether the following graphs G and H are Isomorphic or not. [6] [Figure: Graph G and Graph H] b) Find out if the graph below is Eulerian. If so, write the sequence of vertices of an Eulerian circuit. If not, explain why it isn't Eulerian. [4] [CO3] [Figure: A connected graph with vertices a, b, c, d, e, f, g, h] 3. a) Apply Kruskal's algorithm to construct a spanning tree for the given weighted graph [7] [Figure: A weighted undirected graph with nodes a, b, c, d, e, f, g and weighted edges] b) In the road network of Bangladesh, vertices represent major intersections in cities such as Dhaka, Chattogram, Rajshahi and edges represent roads connecting them. Some roads are one-way (certain roads in Dhaka city) while others are two-way highways (Dhaka-Chattogram highway). Assume that there is at most one road connecting any two intersections. What type of graph is used to model this road network? Justify your answer. [3] 4. a) Consider a group of 7 students where each student writes letters to exactly 3 other students and, at the same time, receives letters from exactly 3 students. Is it possible to model this situation using a graph? If possible to model, then draw the graph. If you think it's not possible then explain with proof why it is not possible. [3] b) "The Bengal Express" is a logistics company based in Dhaka. They need to map out the most efficient delivery route to different regional hubs across Bangladesh. You have been provided with the highway network map, where the cities represent nodes and the two-way highways represent undirected edges. The driving distances between the connected cities are given in kilometers. [7] [CO3] The Highway Network Data: Node | Regional Hub | Connecting Highways & Distances (km) A | Dhaka | B (120), C (150), D (80) B | Mymensingh | A (120), E (110) C | Sylhet | A (150), E (190), F (210) D | Comilla | A (80), G (100), H (140) E | Bogura | B (110), C (190), F (105) F | Rangpur | E (105), C (210) G | Chittagong | D (100), H (90) H | Cox's Bazar | D (140), G (90) Now, apply the shortest path algorithm to find the shortest path from Dhaka to the Rangpur regional hub along with the distance in km.