Discrete Mathematics
CSE · Final · Spring 25
Paper 2 of 3Batch 66 · Ferdosh RiyadSwitch
Batch 66
Paper 2 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 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
1. 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: Undirected weighted graph with nodes A, B, C, D, E, F and weighted edges between them]
2. b) Justify whether the graph is Bipartite graph or not. | [4] |
[Figure: Undirected graph with vertices a, b, c, d, e, f, g, h, i, j, k, l, m, n]
3. a) Prove whether the graphs are isomorphic or not. | [6] | CO3
[Figure: Two graphs labeled Graph- G and Graph- H]
3. 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.
| [6] | CO3
[Figure: Undirected weighted graph representing zones a to i with edge weights]
4. 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.
| [4] |