AL-401 Introduction to Discrete Structure and Linear Algebra - Nov 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
   aProve that: i) $A - (B \cap C) = (A - B) \cup (A - C)$ ii) $A \times (B \cap C) = (A \times B) \cap (A \times C)$
   How to answer

   • Part (i): Show $x \in A - (B \cap C) \iff x \in A \land x \notin (B \cap C)$.
   • Apply De Morgan's laws: $x \notin B \lor x \notin C$, distribute conjunction over disjunction to get $(A - B) \cup (A - C)$.
   • Part (ii): Take an ordered pair $(x, y) \in A \times (B \cap C) \iff x \in A \land y \in (B \cap C)$.
   • Use $y \in B \land y \in C$, distribute $(x \in A \land y \in B) \land (x \in A \land y \in C)$ to conclude $(A \times B) \cap (A \times C)$.
2. 7 Marks
   bWith the help of Venn-diagram, prove that $$(A \cup B)' = A' \cap B' \text{ and } (A \cap B)' = A' \cup B'$$
   How to answer

   • Draw universal set $U$ containing overlapping sets $A$ and $B$.
   • Shade regions representing $A \cup B$ and its complement $(A \cup B)'$.
   • Shade $A'$, $B'$, and show their intersection equals the region outside $A \cup B$.
   • Similarly sketch diagrams for $(A \cap B)'$ and $A' \cup B'$ showing region equivalence.
3. 7 Marks
   aConsider the set $Z$ of integers $m > 1$. We say that $x$ is congruent to $y$ modulo $m$ written as $x \equiv y \pmod m$ If $x - y$ is divisible by $m$. Show that this defines an equivalence relation on $Z$.
   How to answer

   • Define equivalence relation: reflexive, symmetric, and transitive.
   • Reflexive: $x - x = 0 = 0 \cdot m$, so $x \equiv x \pmod m$.
   • Symmetric: If $m \mid (x - y)$, then $x - y = km \implies y - x = (-k)m$, so $m \mid (y - x)$.
   • Transitive: If $m \mid (x - y)$ and $m \mid (y - z)$, then $(x - y) + (y - z) = x - z = (k_1 + k_2)m$, so $m \mid (x - z)$.
   • Conclude that congruence modulo $m$ is an equivalence relation.
4. 7 Marks
   bLet $D_m$ denotes the positive divisors of $m$ ordered by divisibility. Draw the Hasse diagrams of the following: i) $D_{15}$ ii) $D_{24}$
   How to answer

   • Find divisors: $D_{15} = \{1, 3, 5, 15\}$ and $D_{24} = \{1, 2, 3, 4, 6, 8, 12, 24\}$.
   • Identify covering relations for $D_{15}$: $1 \to 3$, $1 \to 5$, $3 \to 15$, $5 \to 15$ (rhombus shape).
   • Identify covering relations for $D_{24}$: $1 \to 2, 3$; $2 \to 4, 6$; $3 \to 6$; $4 \to 8, 12$; $6 \to 12$; $8 \to 24$; $12 \to 24$.
   • Draw clear Hasse diagrams with elements as vertices and covering relations as upward-directed lines.
5. 7 Marks
   aConsider the set $Q$ of rational numbers and let $*$ be the operation on $Q$ defined by: $$a * b = a + b - ab$$ i) Is $(Q, *)$ a semi-group. Is it commutative. ii) Find the identity element for $*$. iii) Do any elements in $Q$ have inverse? What is it?
   How to answer

   • Check associativity: verify $(a * b) * c = a * (b * c) = a + b + c - ab - bc - ca + abc$. Hence, it is a semi-group.
   • Check commutativity: $a * b = a + b - ab = b + a - ba = b * a$. Thus, it is commutative.
   • Find identity $e$: $a * e = a \implies a + e - ae = a \implies e(1 - a) = 0 \implies e = 0$.
   • Find inverse: $a * x = 0 \implies a + x - ax = 0 \implies x(1 - a) = -a \implies x = \frac{a}{a - 1}$ for all $a \neq 1$. Element $1$ has no inverse.
6. 7 Marks
   bDefine Ring with example. Also explain Commutative ring and ring homomorphism.
   How to answer

   • Define Ring $(R, +, \cdot)$ with axioms: $(R, +)$ is abelian group, $(R, \cdot)$ is semigroup, and multiplication distributes over addition.
   • Give standard example (e.g., $(\mathbb{Z}, +, \cdot)$).
   • Define Commutative Ring: $a \cdot b = b \cdot a$ for all $a, b \in R$.
   • Define Ring Homomorphism $f: R \to S$: $f(a + b) = f(a) + f(b)$ and $f(a \cdot b) = f(a) \cdot f(b)$.
7. 7 Marks
   aSolve the following recurrence relations $$a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}, a_0 = 0, a_3 = 3, a_5 = 10$$
   How to answer

   • Form characteristic equation: $r^3 - 3r^2 + 3r - 1 = 0 \implies (r - 1)^3 = 0$.
   • Roots are $r = 1, 1, 1$ (multiplicity 3).
   • Write general solution: $a_n = c_1 + c_2 n + c_3 n^2$.
   • Apply conditions: $a_0 = 0 \implies c_1 = 0$.
   • Solve system with $a_3 = 3c_2 + 9c_3 = 3$ and $a_5 = 5c_2 + 25c_3 = 10$.
   • Find $c_2 = -0.5$ (or fraction) and $c_3 = 0.5$, then write final $a_n$.
8. 7 Marks
   bShow that $$((p \lor q) \land \sim(\sim p \land (\sim q \lor \sim r))) \lor (\sim p \land \sim q) \lor (\sim p \land \sim r) \equiv \text{T}$$ is a tautology by laws of algebra of propositions.
   How to answer

   • Let $A = (p \lor q) \land \sim(\sim p \land (\sim q \lor \sim r))$.
   • Notice $(\sim p \land \sim q) \lor (\sim p \land \sim r) \equiv \sim p \land (\sim q \lor \sim r)$ by distributive law.
   • Let $B = \sim p \land (\sim q \lor \sim r)$, then expression simplifies using $A \lor B$.
   • Apply De Morgan's and complement laws to show equivalence to True (T).
9. 7 Marks
   aObtain the conjunctive normal form of i) $p \land (p \implies q)$ ii) $\sim p \implies [r \land (p \implies q)]$
   How to answer

   • Part (i): Replace $p \implies q$ by $\sim p \lor q$. Expression is already $p \land (\sim p \lor q)$, which is in CNF.
   • Part (ii): Eliminate conditionals: $\sim(\sim p) \lor [r \land (\sim p \lor q)] \equiv p \lor [r \land (\sim p \lor q)]$.
   • Distribute $\lor$ over $\land$: $(p \lor r) \land (p \lor \sim p \lor q)$.
   • Simplify if required or state as CNF: $(p \lor r)$.
10. 7 Marks
    bCheck for Euler and Hamiltonian graphs:

    

    How to answer

    • List degrees of all vertices: $\deg(V_1)=2$, $\deg(V_2)=4$, $\deg(V_3)=3$, $\deg(V_4)=3$, $\deg(V_5)=2$ (based on the given graph edges).
    • Check Euler graph criteria: A connected graph is Eulerian iff every vertex has even degree. Since vertices $V_3, V_4$ have odd degrees, it is not Eulerian (it has an Euler path between $V_3$ and $V_4$).
    • Check Hamiltonian graph: Look for a cycle visiting every vertex exactly once. E.g., $V_1 - V_2 - V_5 - V_4 - V_3 - V_1$ forms a Hamiltonian cycle.
    • Conclude: The graph is Hamiltonian, but not Eulerian.
11. 7 Marks
    aWhat is coloring problem? Hence define coloring of graph.
    How to answer

    • Explain the graph coloring problem: assigning colors to graph elements subject to certain constraints.
    • Define vertex coloring: an assignment of colors to vertices such that no two adjacent vertices share the same color.
    • Define chromatic number $\chi(G)$ as the minimum number of colors needed to color graph $G$.
12. 7 Marks
    bSolve the simultaneous equations: $$25x + 15y - 5z = 35$$ $$15x + 18y + 0 \cdot z = 33$$ $$-5x + 0 \cdot y + 11z = 6$$ Using Cholesky Decomposition.
    How to answer

    • Write system as $Ax = b$ where $A = \begin{pmatrix} 25 & 15 & -5 \\ 15 & 18 & 0 \\ -5 & 0 & 11 \end{pmatrix}$. Note $A$ is symmetric and positive definite.
    • Factor $A = LL^T$ where $L = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix}$.
    • Calculate entries: $l_{11} = 5$; $l_{21} = 3$, $l_{31} = -1$; $l_{22} = \sqrt{18 - 9} = 3$; $l_{32} = (0 - (-3))/3 = 1$; $l_{33} = \sqrt{11 - (1 + 1)} = 3$.
    • Solve $L z' = b$ by forward substitution.
    • Solve $L^T x = z'$ by back substitution to obtain $x, y, z$.
13. 7 Marks
    aWhat is null hypothesis? What is its significance in statistical variance?
    How to answer

    • Define null hypothesis ($H_0$): assertion of no difference, no effect, or no relationship in a population.
    • Explain role in hypothesis testing as a default baseline to be tested against an alternative ($H_1$).
    • Explain its significance in variance analysis (ANOVA): $H_0$ states all group means/variances are equal, tested using F-distribution.
14. 7 Marks
    b

    An agricultural research organization wants to study the effect of four types of fertilizers on the yield of crop. It divided the entire field into 24 plots of land and used fertilizer at random in 6 plots of land. Part of calculations are given below:

    Source of Variation	Sum of Squares	Degree of freedom	Mean Squares	Test Statistic
    fertilizers	2940	3	-	5.99
    Within groups	-	-	-
    Total	6212

    i) Fill in the blanks in the ANOVA table. ii) Test at $\alpha = 0.5$, whether the fertilizers differ significantly.

    How to answer

    • Compute $SS_{within} = 6212 - 2940 = 3272$.
    • Degrees of freedom: Total $df = 24 - 1 = 23$; Within groups $df = 23 - 3 = 20$.
    • Mean Squares: $MS_{fertilizers} = 2940 / 3 = 980$; $MS_{within} = 3272 / 20 = 163.6$.
    • Compute F-ratio: $F = 980 / 163.6 \approx 5.99$.
    • Compare calculated $F$ with critical value at the specified $\alpha$ level to conclude whether fertilizers differ significantly.
15. 7 Marks
    aA coin was tossed 400 times and the head turned up 216 times. Test the hypothesis that the coin is unbiased.
    How to answer

    • Null hypothesis $H_0: p = 0.5$ (coin is unbiased) vs $H_1: p \neq 0.5$.
    • Sample proportion $\hat{p} = 216 / 400 = 0.54$.
    • Standard error $SE = \sqrt{\frac{0.5 \times 0.5}{400}} = \frac{0.5}{20} = 0.025$.
    • Test statistic $z = \frac{0.54 - 0.50}{0.025} = 1.6$.
    • Since $|z| = 1.6 < 1.96$ at $5\%$ level of significance, do not reject $H_0$. The coin can be considered unbiased.
16. 7 Marks
    bFind the singular value decomposition of the matrix: $$A = \begin{bmatrix} -4 & -7 \\ 1 & 4 \end{bmatrix}$$
    How to answer

    • Calculate $A^T A = \begin{bmatrix} -4 & 1 \\ -7 & 4 \end{bmatrix} \begin{bmatrix} -4 & -7 \\ 1 & 4 \end{bmatrix} = \begin{bmatrix} 17 & 32 \\ 32 & 65 \end{bmatrix}$.
    • Find eigenvalues of $A^T A$: $\det(A^T A - \lambda I) = \lambda^2 - 82\lambda + 81 = 0 \implies \lambda_1 = 81, \lambda_2 = 1$.
    • Find singular values: $\sigma_1 = 9, \sigma_2 = 1$, so $\Sigma = \begin{bmatrix} 9 & 0 \\ 0 & 1 \end{bmatrix}$.
    • Find orthonormal eigenvectors of $A^T A$ to construct matrix $V$.
    • Calculate left singular vectors $u_i = \frac{1}{\sigma_i} A v_i$ to form orthogonal matrix $U$.
    • Express final decomposition $A = U \Sigma V^T$.