CS-302 Discrete Structure - Dec 2023 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
   aOut of 120 students surveyed, it was found that 20 students have studied French, 50 students have studied English, 70 students have studied Hindi, 5 have studied English and French, 20 have studied English and Hindi, 10 have studied Hindi and French, only 3 students have studied all the three languages. Find how many students have studied:

   1. i)Hindi alone
   2. ii)French alone
   3. iii)English, but not Hindi
   4. iv)Hindi, but not French
   How to answer

   • Define sets E, H, F and use inclusion-exclusion for surveyed counts
   • Compute only-Hindi = |H| - |EfH| - |HfF| + |all three|
   • Compute only-French and English-but-not-Hindi, Hindi-but-not-French similarly
   • Substitute numbers: 20 French, 50 English, 70 Hindi, 5,20,10 pairwise, 3 all three
2. 7 Marks
   bIf R be a relation in the set of integers Z defined by $R = \{(x, y) : x \in Z, y \in Z, (x-y) \text{ is multiple of } 3\}$. Show that it is an equivalence relation.
   How to answer

   • Define R as congruence modulo 3 on Z
   • Show reflexive: (x-x)=0 divisible by 3
   • Show symmetric: if 3|(x-y) then 3|(y-x)
   • Show transitive: if 3|(x-y) and 3|(y-z) then 3|(x-z)
3. 7 Marks
   aIf $f : R \rightarrow R$ $f(x) = \begin{cases} 3x-12, & x > 3 \\ 2x^{2}+3, & -2 < x \le 3 \\ 3x^{2}-7, & x \le -2 \end{cases}$ find $f^{-1}(3), f^{-1}(0), f^{-1}(-2).$
   How to answer

   • Consider piecewise definition on x>3, -2<xa43, xa4-2
   • Solve f(x)=3,0,-2 in each branch and retain admissible x
   • Collect pre-images for each value
   • State $f^{-1}$ sets
4. 7 Marks
   bShow that $1^{2} + 2^{2} + 3^{2} + ... + n^{2} = \dfrac{n(n+1)(2n+1)}{6}, n \ge 1$ by mathematical induction
   How to answer

   • Verify base case n=1
   • Assume true for n=k (induction hypothesis)
   • Add $(k+1)^2$ and simplify to formula for k+1
   • Conclude by mathematical induction
5. 7 Marks
   aProve that $F = \{a + b\sqrt{2}; a, b \text{ rational}\}$ is a field.
   How to answer

   • Show closure under addition and multiplication
   • Verify field axioms: associativity, identity, inverses
   • Show existence of multiplicative inverse using rationalization with $\sqrt{2}$
   • Conclude $F$ is subfield of reals
6. 7 Marks
   bDefine the following

   1. i)Symmetric Group
   2. ii)Normal Subgroup
   3. iii)Homomorphism
   How to answer

   • Define symmetric group as permutations under composition
   • Define normal subgroup via $gHg^{-1}=H$
   • Define homomorphism preserving operation
7. 7 Marks
   aConstruct the truth table of the following formula:

   1. i)$\sim (p \vee (q \vee r)) \Leftrightarrow ((p \vee q) \wedge (p \vee r))$
   2. ii)$(\sim q \Rightarrow \sim p) \Rightarrow (p \Rightarrow q)$
   How to answer

   • List all 8 assignments for p,q,r
   • Evaluate inner disjunctions/conjunctions and implications
   • Compare LHS and RHS for equivalence / check tautology
   • Present complete truth table
8. 7 Marks
   bWrite the negation of the following.

   1. i)If the determinant of a system of linear equations is zero then either the system has no solution or has an indefinite no. of solutions.
   2. ii)Either today is not a Sunday or today is not a Wednesday.
   How to answer

   • Translate 'if-then' and 'either-or' into propositional form
   • Apply De Morgan and implication negation rules
   • Write negated statement with quantifiers/connectives reversed
   • Give final negation in English
9. 7 Marks
   aShow that the proposition $\neg(p \wedge q)$ and $\neg p \vee q$ are logically equivalent.
   How to answer

   • Recall $\neg(p\wedge q) \equiv \neg p \vee \neg q$ is De Morgan form
   • Construct 4-row truth table for p,q
   • Show columns for both propositions match
   • Conclude logical equivalence
10. 7 Marks
    bObtain the conjunctive normal form of

    1. i)$p \wedge (p \Rightarrow q)$
    2. ii)$\sim p \Rightarrow [r \wedge (p \Rightarrow q)]$
    How to answer

    • Replace $p\Rightarrow q$ by $\neg p \vee q$
    • Apply distributive / De Morgan laws
    • Express as conjunction of disjunctions of literals
    • Simplify to CNF
11. 7 Marks
    aDetermine whether the graphs F1 and F2 are isomorphic.

    

    How to answer

    • Count vertices and edges and degree sequences of F1 and F2
    • Check necessary conditions for isomorphism
    • Attempt bijection preserving adjacency or find invariant violation
    • Conclude isomorphic or not
12. 7 Marks
    bFind an Euler Path in the graph below.

    

    How to answer

    • Compute degree of each vertex A,B,C,D,E,F,G
    • Identify 0 or 2 odd-degree vertices for Euler trail
    • Trace trail using Fleury's algorithm without repeating edges
    • Present vertex sequence covering all edges
13. 7 Marks
    aDefine a lattice. Let $(L, \le, \vee, \wedge)$ be a lattice, and $a, b, c, d \in L$ be such that $a \le b$ and $c \le d$. Show that $a \vee c \le b \vee d$ and $a \wedge c \le b \wedge d$.
    How to answer

    • Define lattice as poset with lub and glb / algebraic axioms
    • Use $a\le b$ implies $a\vee d \le b\vee d$ etc.
    • Show $a\vee c \le b\vee d$ by transitivity of order
    • Dually show $a\wedge c \le b\wedge d$
14. 7 Marks
    bShow that $D_{12}$ and $D_{18}$ are isomorphic lattices. Further, show that none is isomorphic to the lattice $D_{20}$.
    How to answer

    • Recall D_n is divisor lattice under divisibility
    • List divisors of 12, 18, 20 and draw Hasse structure
    • Give explicit order-preserving bijection between D12 and D18
    • Show invariant (e.g., number of elements / structure) prevents isomorphism with D20
15. 7 Marks
    aShow that $a_{n} = c_{1}2^{n} + c_{2}4^{n}$ is a solution of the recurrence relation $a_{n} - 6a_{n-1} + 8a_{n-2} = 0$.
    How to answer

    • Substitute $a_n=c_12^n+c_24^n$ into LHS
    • Compute $a_{n-1}, a_{n-2}$ terms
    • Simplify to show $a_n-6a_{n-1}+8a_{n-2}=0$
    • Conclude it satisfies recurrence
16. 7 Marks
    bFind the sequence having the generating function $G(x)$ given by $\dfrac{x}{1-2x}$.
    How to answer

    • Write $x/(1-2x)=x\cdot 1/(1-2x)$
    • Expand $1/(1-2x)=\sum 2^n x^n$
    • Multiply by x to shift index
    • Identify sequence $a_n = 2^{n-1}$ for $n\ge1$