Skip to content

Discrete Mathematics

CSE · Final · Spring 25

Paper 3 of 3Batch 66 · Rakibul HasanSwitch

Batch 66

Paper 3 of 3

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 Semester Examination, Spring 2025 Course Code: CSE212, Course Title: Discrete Mathematics Level 2: Term: 1 Batch: 66 Time: 2:00 Hrs Marks: 40 Answer ALL the 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) Conjecture a formula for 1/2 + 1/4 + 1/8 + ....... + 1/2^n where n is a positive integer and prove the formula using Mathematical Induction. [6] CO2 b) Identify the properties of the relation R on A = {1, 2, 3, 4} if R is {(a, b) | a = b+1}. [4] 2. a) Consider the following undirected weighted graph. Apply Dijkstra on this graph to simulate the shortest path from A to F. [6] CO3 [Figure: An undirected weighted graph with vertices A, B, C, D, E, F and weighted edges between them] b) Justify whether the graph is Bipartite graph or not. [4] CO3 [Figure: A complex undirected graph with vertices labeled a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] 3. a) Prove whether the graphs are isomorphic or not. [6] CO3 [Figure: Two graphs labeled Graph-G with vertices 1, 2, 3, 4, 5 and Graph-H with vertices A, B, C, D, E] b) Justify whether the following graph has Euler Cycle, Euler Path or none of them. [4] [Figure: Two graphs labeled Graph-G and Graph-H] 4. a) The city of Graphville is planning to lay down fiber-optic cables to connect its 9 administrative zones. Each zone is represented as a node in the map below. The roads between the zones (edges) are already established, and the cost of laying fiber along each road (weight) is known and shown on the map. As the chief network engineer of Graphville, your goal is to ensure that every zone is connected to the fiber-optic network directly or indirectly, but you must minimize the total cost of laying the cables. Redundant paths are to be avoided to save budget, so no cycles should be present in the final layout. You are asked to: 1. Identify the set of roads (edges) you will choose to lay fiber such that all zones are connected with minimum total cost (i.e., Minimum Spanning Tree) using Prim's Algorithm. 2. Calculate the total cost of laying the cables using your selected connections. [Figure: A weighted undirected graph showing zones connected by edges with weights] b) Consider the following scenario: A Job Fair is organized by DIU. There are two distinct groups attending the event. Group A (Students) consist of 4 final-year computer science students - Ramit, Alo, Mustahid and Foysal. Group B (Companies) consist of 3 tech companies - Innovix, CodeCraft, and NexaSoft. Each student is required to connect with every company for interviews, and each company wants to interview every student. This creates a situation where every student must be connected to every company, but students do not connect with other students, and companies do not connect with other companies. i) Represent this phenomena with an undirected graph ii) Define the type of graph iii) Prove handshaking theorem of that graph.