Skip to content

Discrete Mathematics

CSE · Final · Fall 24

Paper 2 of 3Batch 65 · SUPAN ROYSwitch

Batch 65

Paper 2 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, Fall 2024 Course Code: CSE212, Course Title: Discrete Mathematics Level: 2 Term: 1 Batch: 65 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) Determine whether the given relation is reflexive, symmetric, transitive, or none of these. Justify your answers. i. C is the circle relation on the set of real numbers: For every x, y in R, x C y <=> x^2 + y^2 = 1. ii. D is the "divides" relation on Z^+: For all positive integers m and n, m D n <=> m | n. [4] [CO2] 1. b) Use mathematical induction to prove that for all non-negative integers n, 1 + 1/2 + 1/2^2 + 1/2^3 + ... + 1/2^n = 2 - 1/2^n. [6] [CO2] 2. a) Prove whether the following graphs G and G' are isomorphic or not? [Figure: Two graphs G and G' with vertices labeled, showing their connectivity structure] [4] [CO3] 2. b) Apply the concept of Dijkstra's algorithm to find the shortest path from a to z. [Figure: A weighted connected graph with vertices a, b, c, d, e, f, g, z and weighted edges between them] [6] [CO3] 3. a) Justify whether the following graphs are bipartite or not. [Figure: Two graphs labeled Graph: A and Graph: B with various vertices such as v1, v2, v3, etc.] [7] [CO3] 3. b) Draw these Graphs- i. C_5 ii. K_{4,3} iii. W_7 [3] [CO3] 4. a) Apply Prim's algorithm on the following graph starting at node a to construct a minimum spanning tree indicating the order in which edges are added to form each tree, and find the weight of the tree. [Figure: A weighted undirected graph with nodes a, b, c, d, e, f, g and edges with weights 1, 7, 4, 3, 2, 5, 6, 9, 10, 8] [7] [CO3] 4. b) Draw a graph from the following adjacency matrix. [ 0 0 0 1 2 ] [ 0 0 0 1 1 ] [ 0 0 0 2 1 ] [ 1 1 2 0 0 ] [ 2 1 1 0 0 ] [3] [CO3]