Engineering B.E. (Computer Engineering) Sem 3 Discrete Structures and Graph Theory May 2026 Question Paper - Mumbai University | munotes

Questions asked in this paper

• N.B. (1) Q.1 is compulsory. (2) Attempt any three out of the remaining. (3) Figures to the right indicate full marks. (4) Assume suitable data if necessary.

Q.1 Q.1 15 Marks

1. a) A digital geometry learning platform groups polygons based on the number of sides for automatic classification and retrieval. Let A be the set of all polygons. A relation R is defined on A as: R = {(P₁, P₂): P₁ and P₂ have the same number of sides}. Based on this classification system: (1) Analyze whether the relation R is an equivalence relation on A. (2) Verify the properties of reflexivity, symmetry, and transitivity. (3) Construct suitable equivalence classes for triangles, quadrilaterals, and pentagons. (4) Interpret how equivalence relations help organize geometric data in digital systems. 5 marks
   Read the model answer
2. b) A software security system uses logical rules to decide whether access should be granted, denied, or forwarded for further verification. Consider the following logical expressions: ((p → q) → r) and (p ∧ ¬q) ∨ r. Using a series of logical equivalences, prove that the two expressions are logically equivalent. Also interpret how logical equivalence helps simplify decision rules in software systems. 5 marks
   Read the model answer
3. c) A quality control department stores 10 pairs of socks of different colors in a drawer for packaging verification. Using the Pigeonhole Principle, analyze the minimum number of socks that must be selected randomly to guarantee that at least one matching pair of the same color is obtained. Justify your answer with suitable reasoning. 5 marks
   Read the model answer

Q.2 Q.2 15 Marks

1. a) A pharmaceutical company conducts a drug trial on 1000 people to analyze the side effects of a newly developed medicine. The following observations are recorded: 122 people develop symptom A; 88 people develop symptom B; 112 people develop symptom C; 27 people develop both symptoms A and B; 29 people develop both symptoms A and C; 32 people develop both symptoms B and C; 10 people develop all three symptoms A, B, and C. Using the Principle of Inclusion and Exclusion: (1) Analyze how many people develop at least one symptom. (2) Determine the number of people who show exactly one symptom. (3) Construct a Venn diagram and fill all regions appropriately.
   Read the model answer
2. b) A retail store offers seasonal discounts on clothing items. A customer wants to purchase a shirt priced at Rs.1000. The store first provides a 15% discount, after which an 8% sales tax is applied to the discounted price. Based on this shopping scenario: (1) Develop suitable mathematical functions representing the discount process and the tax calculation process. (2) Construct the composite function representing the final cost of the shirt. (3) Determine the final amount to be paid by the customer. (4) Analyze how composite functions help automate billing systems in retail applications. 7 marks
   Read the model answer

Q.3 Q.3 15 Marks

1. a) A domestic airline company maintains a directed flight network among four cities: V = {a, b, c, d}. The direct flight connections are represented by the relation: R = {(a, b), (b, d), (d, c), (d, a)}. The company wants to analyze all possible direct and indirect travel routes, including circular journeys. Based on the given flight network: (1) Identify and explain the concept of reachability / transitive closure used in the graph. (2) Determine all possible ordered pairs of cities connected through: direct routes, routes with layovers, and circular routes. (3) Analyze how graph connectivity helps optimize airline route planning. (4) Represent the final connectivity relation for the graph. 8 marks
   Read the model answer
2. b) A cloud access-control system organizes permission levels using divisibility-based hierarchy. The permission levels are: A = {1, 2, 3, 6, 12, 24, 36, 72}. A relation R is defined on A as: (x, y) ∈ R if x | y. Based on this hierarchy: (1) Write all ordered pairs of relation R. (2) Construct the Hasse Diagram of the poset. (3) Analyze whether the given poset forms a lattice. (4) Justify your answer using suitable meet and join examples. 7 marks
   Read the model answer

Q.4 Q.4 15 Marks

1. a) A cryptographic system uses non-zero residue classes modulo 7 for secure key generation. Consider the set: G = {1, 2, 3, 4, 5, 6} under multiplication modulo 7. Based on this system: (1) Construct the multiplication table of G under multiplication modulo 7. (2) Determine the multiplicative inverses of 2, 3, 5 and 6. (3) Analyze whether G forms a cyclic group. (4) If it is cyclic, identify at least one generator and justify your answer.
   Read the model answer
2. b) A data analyst observes that the cumulative computational cost of a repeated process is modeled by the series: Σ r(r + 3), r = 1 to n. The analyst claims that for every positive integer n, Σ r(r + 3) (r = 1 to n) = (1/3) n(n + 1)(n + 5), n ≥ 1, n ∈ N. Using the principle of mathematical induction: (1) Verify the result for the base case. (2) Prove the inductive step. (3) Conclude that the formula is valid for all n ≥ 1. (4) Interpret how induction helps validate formulas in algorithm analysis. 7 marks
   Read the model answer

Q.5 Q.5 15 Marks

1. a) A computer networking company proposes two communication network layouts represented by graphs G₁ and G₂. The organization wants to verify whether both network structures provide the same connectivity pattern even though the device labels are different. The graphs are represented as: V(G₁) = {A, B, C, X, Y, Z}; E(G₁) = {(A, X), (A, Y), (B, X), (B, Y), (C, Y)}; V(G₂) = {1, 2, 3, 4, 5, 6}; E(G₂) = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 5)}. Based on the above network structures: (1) Define isomorphism of graphs. (2) Analyze whether graphs G₁ and G₂ are isomorphic. (3) If they are isomorphic, determine a valid one-to-one correspondence between the vertices. (4) Justify your answer by comparing degree sequence and adjacency preservation. 8 marks
   Read the model answer
2. b) A financial analytics company models the quarterly growth of a digital investment portfolio using a recurrence relation. Let Fₙ represent the portfolio value during the nth quarter. The growth pattern is governed by: Fₙ = 3Fₙ₋₁ + 10Fₙ₋₂ + 7 · 5ⁿ with initial conditions: F₀ = 4, F₁ = -3. Based on this predictive model: (1) Solve the given recurrence relation using an appropriate method. (2) Determine the general expression for Fₙ. (3) Analyze the effect of the exponential forcing term 7 · 5ⁿ on the sequence growth. (4) Interpret how recurrence relations are useful in financial forecasting and computational modeling. 7 marks
   Read the model answer

Q.6 Q.6 15 Marks

1. a) A cryptographic system uses arithmetic operations on residue classes modulo 4 for encoding and verification. Consider the set: Z₄ = {0, 1, 2, 3} with addition and multiplication defined modulo 4. Based on this algebraic structure: (1) Construct the addition and multiplication tables for Z₄. (2) Verify whether Z₄ satisfies the required ring properties. (3) Analyze the role of additive identity, additive inverse, multiplicative associativity, and distributive laws. (4) Conclude whether Z₄ forms a ring under addition and multiplication modulo 4. 8 marks
   Read the model answer
2. b) A city transport authority is analyzing a road network connecting six important locations A, B, C, D, E, and F. The network is represented by the following graph: Graph. Based on the given road network: (1) Determine whether the graph has an Euler Path. (2) Determine whether the graph has an Euler Circuit. (3) Determine whether the graph has a Hamiltonian Path. (4) Determine whether the graph has a Hamiltonian Circuit. (5) Justify your answer using degree of vertices and graph traversal conditions. 7 marks
   Read the model answer

Read from the scan above, so a character or two may differ. The scan is the original.