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

Questions asked in this paper

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

Q.1 Q.1 (Attempt any three out of six sub questions) 15 Marks

1. a) A student-feedback system groups teacher responses using the rule: Two responses x and y are "similar" if they fall in the same satisfaction band (e.g., 1-2 = Low, 3 = Medium, 4-5 = High). (i) Using definitions of reflexive, symmetric, transitive, determine whether "similarity" is an equivalence relation. (ii) Explain the classroom-level meaning of each property. (iii) Discuss how violating any property affects AI-based feedback analytics and dashboard reports.
   Read the model answer
2. b) A college bus attendance system gives "Boarded = True" when: P: The student taps RFID card; Q: Bus mentor manually verifies student; R: The system logs boarding record. The transport officer rewrites: (P ∨ Q) → R ≡ (P → R) ∧ (Q → R). (i) Prove the above using logical equivalence laws step-by-step. (ii) Explain how this version ensures no boarding method is ignored, improves data consistency, and reduces false "absent" cases.
   Read the model answer
3. c) A programming contest has 240 participants and 12 judging terminals. (i) Using Pigeonhole Principle, find the minimum number of contestants who must end up using the same terminal. (ii) Explain how this insight helps in contest scheduling, load balancing, and avoiding terminal bottlenecks.
   Read the model answer
4. d) A Cybersecurity lab access is granted if: P: Student has lab clearance; Q: Student has signed NDA; R: Student completed safety briefing. Access expression: A = (P ∧ Q) ∨ (P ∧ R). (i) Construct truth table for A. (ii) Identify combinations where access is wrongly granted. (iii) Explain consequences for security, safety compliance, and audit records.
   Read the model answer
5. e) Students are assigned to specialization tracks based on the following rule: Score in Coding >= 80 → Software Track; Score in Networks >= 75 → Network Security; Score in Math >= 85 → Data Science (Priority: Data Science > Software > Network Security). Given sample data (Coding, Networks, Math): S1: (85, 60, 70); S2: (65, 80, 90); S3: (82, 78, 88); S4: (78, 76, 60). (i) Map each student to a track. (ii) Check if the mapping is function / one-one / onto / many-one. (iii) Explain how these properties impact batch size planning, mentor allocation, and fairness.
   Read the model answer

Q.2 Q.2 15 Marks

1. a) A campus event app records students who use three app sections: E: Event Announcements; C: Clubs & Communities; R: Reels / Short videos. Survey data: Category, Count: E 140; C 110; R 120; E ∩ C 65; E ∩ R 70; C ∩ R 55; Total Students 200. (i) Using inclusion-exclusion, compute how many students use all three sections. (ii) Find students who use only one section. (iii) Explain how this analysis helps app developers and event committees design targeted notifications and UI improvements. 8 marks
   Read the model answer
2. b) A university assigns raw marks to final grades using: Moderation function M(x) = x + 5; Weight conversion W(x) = 0.4x. Compute the compositions: (i) W ∘ M (ii) M ∘ W (iii) M ∘ M (iv) W ∘ W. Interpret each composition in the grading context, and discuss which are academically meaningful and which may distort scores. 7 marks
   Read the model answer

Q.3 Q.3 15 Marks

1. a) A Data Science program has a prerequisite network among modules: M1: Python Basics; M2: DS Foundation; M3: Machine Learning; M4: Deep Learning; M5: Deployment. Given relation R = {(1,2), (2,3), (3,4), (4,5), (1,1), (3,3), (5,5)}. (i) Apply Warshall's Algorithm to compute transitive closure. (ii) For each Mi, list all modules it can unlock. (iii) Identify root modules and terminal modules. (iv) Explain how this helps curriculum planners maintain valid learning paths. 8 marks
   Read the model answer
2. b) Data storage providers offer plans of sizes: S = {1 TB, 2 TB, 4 TB, 8 TB, 16 TB}. Relation a | b (a divides b). (i) Draw the Hasse diagram. (ii) List all (a,b) where a divides b. (iii) Check whether S forms a lattice (meet & join for every pair). (iv) Explain impact on designing upgrade/downgrade recommendations and plan combinations in the storage app. 7 marks
   Read the model answer

Q.4 Q.4 15 Marks

1. a) A QR-based token system transforms token number a into: T(a) = (a × k) mod 7, with a ∈ {1.6}. (i) Construct multiplication table (×₇). (ii) Find modular inverses of 2, 3, 5 under mod 7. (iii) Determine if ({1.6}, ×₇) forms a group. (iv) Comment on whether this token transformation ensures reversibility, forgery prevention, and predictable validation. 8 marks
   Read the model answer
2. b) A student deposits savings in a fund according to: Daily saving: Sₙ = 4n - 1. They want to verify if Sₙ is always odd for all natural numbers n. (i) Prove the statement using mathematical induction. (ii) Explain the meaning for planning weekly budgets and long-term savings. 7 marks
   Read the model answer

Q.5 Q.5 15 Marks

1. a) Two lab surveillance networks are modeled as undirected graphs: Graph G₁ (Cameras A,B,C,D): A: B, C; B: A, D; C: A, D; D: B, C. Graph G₂ (Cameras P,Q,R,S): P: Q, R; Q: P, S; R: P, S; S: Q, R. (i) Determine whether G₁ and G₂ are isomorphic. (ii) If yes, provide the mapping. (iii) Explain how detecting isomorphic patterns helps in reusing surveillance layouts and minimizing storage of duplicate designs. 8 marks
   Read the model answer
2. b) A student club records followers using recurrence: Fₙ = 4Fₙ₋₁ - 4Fₙ₋₂, with F₀ = 10 (core team), F₁ = 30 (after first promotion). (i) Solve the recurrence relation. (ii) Describe growth pattern (linear/exponential). (iii) Comment whether such growth is realistic for a campus club in long term. 7 marks
   Read the model answer

Q.6 Q.6 15 Marks

1. a) The college uses modulo-6 operations to rotate lab batches: Addition: a ⊕ b = (a + b) mod 6; Multiplication: a ⊗ b = (a × b) mod 6. (i) Check if (Z₆, ⊕) is an abelian group. (ii) Check closure, associativity of (Z₆, ⊗). (iii) Verify distributive property of ⊗ over ⊕. (iv) Conclude whether (Z₆, ⊕, ⊗) forms a ring, and discuss why this matters in designing timetable rotation logic. 8 marks
   Read the model answer
2. b) A research conference venue is modeled as graph V = {A,B,C,D,E,F} with edges: E = {AB, AC, BC, BD, CE, DE, DF, EF}. (i) Determine existence of Euler Path, Euler Circuit, Hamiltonian Path, Hamiltonian Circuit. (ii) Construct them if they exist. (iii) Explain what this means for planning visitor flow, inspection rounds, and avoiding repeated walking paths. 7 marks
   Read the model answer

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