CS-302 Discrete Structure - Jun 2025 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aConsider three sets $A = \{1, 2, 3, 4, 5\}$, $B = \{3, 4, 5, 6\}$ and $C = \{1, 5, 7\}$. Using Venn diagrams, determine and shade the regions corresponding to $(A \cup B) \cap (B \cap C)$ and $A \cap (B \cup C)$. Verify if these expressions are equivalent by listing the elements.
   How to answer

   • Draw three-circle Venn diagram for sets A, B, and C.
   • Calculate and shade the region corresponding to $(A \cup B) \cap (B \cap C)$.
   • Calculate and shade the region corresponding to $A \cap (B \cup C)$.
   • List elements: $B \cap C = \{5\}$, $(A \cup B) \cap (B \cap C) = \{5\}$.
   • List elements: $B \cup C = \{1, 3, 4, 5, 6, 7\}$, $A \cap (B \cup C) = \{1, 3, 4, 5\}$.
   • Conclude that the two expressions are not equivalent since $\{5\} \neq \{1, 3, 4, 5\}$.
2. 7 Marks
   bDefine and illustrate an equivalence relation by constructing an equivalence relation on the set $S = \{1, 2, 3, 4, 5, 6\}$ where two elements are related if they have the same remainder when divided by 3.
   How to answer

   • Define equivalence relation: reflexive, symmetric, and transitive.
   • Partition set $S = \{1, 2, 3, 4, 5, 6\}$ by remainder mod 3: $[0] = \{3, 6\}$, $[1] = \{1, 4\}$, $[2] = \{2, 5\}$.
   • Construct relation $R = \{(a, b) \in S \times S \mid a \equiv b \pmod 3\}$.
   • List all ordered pairs of $R$.
   • Verify/demonstrate reflexivity, symmetry, and transitivity on $R$.
3. 7 Marks
   aWhat is pigeonhole principle. Prove it by using mathematical induction and use it to show that in a group of 15 people, at least two share the same birth month.
   How to answer

   • State the Pigeonhole Principle formally.
   • Provide inductive proof of the principle with respect to the number of pigeonholes $n$.
   • Identify pigeons (15 people) and pigeonholes (12 months).
   • Apply the principle: since $15 > 12$, by the pigeonhole principle at least $\lceil 15/12 \rceil = 2$ people share the same birth month.
4. 7 Marks
   bExplain a recursively defined function. Solve the recurrence relation $f(n) = f(n - 1) + 3$ with initial condition $f(0) = 2$.
   How to answer

   • Define a recursively defined function (base case + recursive step).
   • Unroll recurrence: $f(n) = f(n-1) + 3 = f(n-2) + 2(3) = \dots = f(0) + 3n$.
   • Substitute $f(0) = 2$ to get closed-form solution: $f(n) = 3n + 2$.
   • Verify solution using induction or substitution.
5. 7 Marks
   aProve that the set $G = \{0, 1, 2, 3\}$ under addition modulo 4 is an abelian group. Identify the identity and inverse elements.
   How to answer

   • Construct the Cayley table (addition modulo 4) for set $G$.
   • Verify Closure: all table entries belong to $G$.
   • Verify Associativity: inherited from standard integer addition modulo 4.
   • Identity element: 0, since $a +_4 0 = 0 +_4 a = a$.
   • Inverse elements: $0^{-1} = 0$, $1^{-1} = 3$, $2^{-1} = 2$, $3^{-1} = 1$.
   • Verify Commutativity: table is symmetric across main diagonal.
   • Conclude that $(G, +_4)$ is an abelian group.
6. 7 Marks
   bDefine a homomorphism between two groups. Verify whether the mapping $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x$ is a homomorphism under addition.
   How to answer

   • Define group homomorphism: A map $f : (G, *) \to (H, \circ)$ satisfying $f(a * b) = f(a) \circ f(b)$ for all $a, b \in G$.
   • Set up the given map: $f : (\mathbb{R}, +) \to (\mathbb{R}, +)$ with $f(x) = 2x$.
   • Evaluate $f(x + y) = 2(x + y) = 2x + 2y$.
   • Evaluate $f(x) + f(y) = 2x + 2y$.
   • Since $f(x + y) = f(x) + f(y)$, conclude that $f$ is a homomorphism under addition.
7. 7 Marks
   aConsider the propositions $p$, $q$ and $r$, where: * $p$ : "It is raining." * $q$ : "I am carrying an umbrella." * $r$ : "I stay dry." Assume the implication $(p \to q) \to r$. Construct a truth table for the expression $(p \to q) \to r$ and determine if it is a tautology or contradiction.
   How to answer

   • List all 8 truth combinations for propositions $p$, $q$, and $r$.
   • Compute the column for $p \to q$ (false only when $p$ is True and $q$ is False).
   • Compute the column for $(p \to q) \to r$.
   • Analyze the resulting column: identify whether values are all True (tautology), all False (contradiction), or mixed (neither/contingency).
   • State conclusion clearly.
8. 7 Marks
   bWhat are predicates in propositional logic? Define universal and existential quantifiers with examples.
   How to answer

   • Define predicate: a statement containing variables that becomes a proposition when values are assigned.
   • Define Universal Quantifier ($\forall$): statement holds for all values in domain; provide example (e.g., $\forall x (x^2 \ge 0)$).
   • Define Existential Quantifier ($\exists$): statement holds for at least one value in domain; provide example (e.g., $\exists x (x + 2 = 5)$).
9. 7 Marks
   aDefine graph theory and explain the basic terminology of graphs such as vertices, edges, degree and adjacency.
   How to answer

   • Define graph $G = (V, E)$.
   • Explain vertices (nodes) and edges (arcs/links).
   • Explain degree of a vertex (in-degree, out-degree for directed, total degree for undirected).
   • Explain adjacency between vertices and incidence between vertices and edges.
   • Provide a simple illustrative example diagram.
10. 7 Marks
    bDefine and give an example of an isomorphic graph pair. Verify isomorphism between two adjacency matrices.
    How to answer

    • Define graph isomorphism: bijection $f : V_1 \to V_2$ preserving adjacency.
    • Provide a simple example of two isomorphic graphs with drawings.
    • Explain adjacency matrix representation $A_1$ and $A_2$.
    • Show verification via permutation matrix $P$: $A_2 = P A_1 P^T$ (or vertex relabeling correspondence).
    • Demonstrate with the chosen example matrices.
11. 7 Marks
    aFor the graph $G$ with vertices $V = \{A, B, C, D\}$ and edges $E = \{(A, B), (B, C), (C, D), (D, A), (A, C)\}$, determine: i) Whether the graph contains a Eulerian path or circuit or not. ii) All Hamiltonian circuits in the graph $G$.
    How to answer

    • Draw graph $G$ with 4 vertices and 5 edges.
    • Calculate degrees: $\deg(A) = 3$, $\deg(B) = 2$, $\deg(C) = 3$, $\deg(D) = 2$.
    • For (i): Exactly two vertices ($A$ and $C$) have odd degrees, so the graph contains a Eulerian path (starting at $A$ and ending at $C$ or vice versa), but no Eulerian circuit.
    • Give an example Eulerian path: $A - B - C - A - D - C$.
    • For (ii): List Hamiltonian circuits (cycles visiting every vertex exactly once and returning to start): e.g., $A - B - C - D - A$ (and its reverse $A - D - C - B - A$).
12. 7 Marks
    bHow many permutations can be formed from the letters of the word "MATHEMATICS" such that all vowels are together?
    How to answer

    • Count letters in "MATHEMATICS": total 11 letters: M:2, A:2, T:2, H:1, E:1, I:1, C:1, S:1.
    • Identify vowels: A, E, A, I (4 vowels: 2 A's, 1 E, 1 I).
    • Group vowels as one unit $(AEAI)$; remaining consonants: M, T, H, M, T, C, S (7 consonants).
    • Total entities to arrange = $7 + 1 = 8$ units with M:2, T:2: $\frac{8!}{2! 2!} = \frac{40320}{4} = 10080$.
    • Arrange vowels internally: $\frac{4!}{2!} = 12$.
    • Total permutations = $10080 \times 12 = 120,960$.
13. 7 Marks
    aWhat is a Hasse diagram? Draw the Hasse diagram for the set $\{1, 2, 3, 6, 9, 18\}$ with the divisibility relation.
    How to answer

    • Define Hasse diagram: a simplified visual representation of a finite partially ordered set (poset) omitting reflexive loops and transitive edges.
    • List covering relations for $S = \{1, 2, 3, 6, 9, 18\}$ under divisibility: $1 \prec 2$, $1 \prec 3$, $2 \prec 6$, $3 \prec 6$, $3 \prec 9$, $6 \prec 18$, $9 \prec 18$.
    • Draw vertices at levels: level 0: 1; level 1: 2, 3; level 2: 6, 9; level 3: 18.
    • Connect the covering pairs with lines oriented upward.
14. 7 Marks
    bDefine a lattice and prove that every finite lattice has a unique least upper bound and greatest lower bound.
    How to answer

    • Define lattice: a poset $(L, \le)$ in which every pair of elements has a unique least upper bound (join $\lor$) and unique greatest lower bound (meet $\land$).
    • Let $L = \{a_1, a_2, \dots, a_n\}$ be a finite lattice.
    • Express the join of all elements: $M = a_1 \lor a_2 \lor \dots \lor a_n$.
    • By associativity and induction, this join exists, is unique, and serves as the unique least upper bound (top element, 1).
    • Similarly, express the meet: $m = a_1 \land a_2 \land \dots \land a_n$, which exists and is the unique greatest lower bound (bottom element, 0).
15. 14 Marks
    Write short notes on (any four) i) Finite state machines as language recognizers ii) Binomial theorem iii) Permutation group iv) Partial Ordering Relation v) Countable and uncountable sets
    How to answer

    • For (i): Define FSM (states, input alphabet, transitions, initial state, accepting states) and how an accepted string ends in a final state.
    • For (ii): State Binomial Theorem $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$ with properties of binomial coefficients.
    • For (iii): Define permutation group $S_n$ (bijections on a set with function composition), symmetric group, and cycle notation.
    • For (iv): Define partial order: reflexive, antisymmetric, and transitive relations with an example like $(\mathbb{Z}^+, |)$.
    • For (v): Define countable set (bijection to a subset of $\mathbb{N}$) and uncountable set (e.g., $\mathbb{R}$ via Cantor's diagonal argument).