AL-401 Introduction to Discrete Structure and Linear Algebra - Jun 2022 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. 14 Marks
   List the 16 different relations on the set $\{0, 1\}$. How many of the 16 different relations on $\{0, 1\}$ contain the pair $(0, 1)$. Which of the 16 relations on $\{0, 1\}$ are reflexive, symmetric and transitive.
   How to answer

   • Enumerate all $2^4 = 16$ subsets of $\{0, 1\} \times \{0, 1\}$
   • Count relations containing $(0, 1)$: $2^3 = 8$
   • Identify relations that satisfy reflexivity, symmetry, and transitivity (equivalence relations): $\{(0,0), (1,1)\}$ and $\{0, 1\} \times \{0, 1\}$
2. 7 Marks
   aShow that the set $S = \{ (1, 3, 5, 7), X_8 \}$ forms a group.
   How to answer

   • Construct Cayley multiplication table modulo 8 for $\{1, 3, 5, 7\}$
   • Show closure property from the table
   • Verify associativity
   • Identify identity element ($e = 1$)
   • Identify inverse of each element (all elements are self-inverse)
3. 7 Marks
   bProve that $n P_n(x) = x P'_n(x) - P'_{n-1}(x)$ using recurrence relation.
   How to answer

   • State standard recurrence relations: $(2n+1)x P_n(x) = (n+1)P_{n+1}(x) + n P_{n-1}(x)$ and $(2n+1)P_n(x) = P'_{n+1}(x) - P'_{n-1}(x)$ or differentiate generating function
   • Differentiate recurrence relation with respect to $x$
   • Manipulate equations to obtain $n P_n(x) = x P'_n(x) - P'_{n-1}(x)$
4. 8 Marks
   aDemonstrate that $p \lor (q \land r)$ and $(p \lor q) \land (p \lor r)$ are logically equivalent. (Using Truth table)
   How to answer

   • Create truth table with columns for $p$, $q$, $r$
   • Evaluate $q \land r$ and then $p \lor (q \land r)$
   • Evaluate $p \lor q$, $p \lor r$, and then $(p \lor q) \land (p \lor r)$
   • Compare the final truth columns for all 8 combinations and conclude equivalence
5. 6 Marks
   bShow that $\neg (p \lor (\neg p \land q))$ and $(\neg p \land \neg q)$ are logically equivalent by developing series of logical equivalence.
   How to answer

   • Apply distributive law inside parentheses: $p \lor (\neg p \land q) \equiv (p \lor \neg p) \land (p \lor q)$
   • Use identity $(p \lor \neg p) \equiv T$: $T \land (p \lor q) \equiv p \lor q$
   • Apply negation: $\neg(p \lor q)$
   • Apply De Morgan's Law: $\neg p \land \neg q$
6. 8 Marks
   aDraw the Hasse diagram for divisibility on the set $\{1, 2, 3, 4, 5, 6\}$.
   How to answer

   • Define divisibility relation pairs on $\{1, 2, 3, 4, 5, 6\}$
   • Identify covering relations (immediate predecessors/successors)
   • Place 1 at bottom level; 2, 3, 5 at level 1; 4, 6 at level 2
   • Connect edges: (1,2), (1,3), (1,5), (2,4), (2,6), (3,6)
7. 6 Marks
   bDefine the terms: Abelian Group, Cyclic Group and Normal Sub group.
   How to answer

   • Define Abelian Group: satisfies commutative property $a * b = b * a$ for all elements
   • Define Cyclic Group: generated by a single element $g$, such that every element is $g^k$
   • Define Normal Subgroup: a subgroup $N \le G$ such that $g N g^{-1} = N$ for all $g \in G$
8. 7 Marks
   aDiscuss various graph terminologies.
   How to answer

   • Define basic terms: vertex, edge, degree of a vertex (in-degree/out-degree)
   • Define path, cycle, simple path, connected/disconnected graphs
   • Explain special graphs: complete graph, bipartite graph, regular graph, tree
   • Provide illustrative sketches for each
9. 7 Marks
   bWhat is coloring problem and hence define coloring of graph?
   How to answer

   • Explain the map coloring problem and its origin
   • Define graph vertex coloring: assignment of colors such that adjacent vertices receive different colors
   • Define chromatic number $\chi(G)$
   • Provide an example graph with its chromatic number
10. 14 Marks
    Solve the system by Cholesky decomposition. $$x + 2y + 3z = 5, \quad 2x + 8y + 22z = 6, \quad 3x + 22y + 82z = -10.$$
    How to answer

    • Write the coefficient matrix $A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 8 & 22 \\ 3 & 22 & 82 \end{bmatrix}$ and vector $B = \begin{bmatrix} 5 \\ 6 \\ -10 \end{bmatrix}$
    • Compute lower triangular matrix $L$ such that $A = L L^T$
    • Solve $L Y = B$ using forward substitution
    • Solve $L^T X = Y$ using back substitution to obtain $(x, y, z)$
11. 14 Marks
    Find the singular value decomposition of the matrix $$A = \begin{bmatrix} 3 & 1 & 1 \\ -1 & 3 & 1 \end{bmatrix}.$$
    How to answer

    • Compute $A A^T$ (size $2 \times 2$) and determine eigenvalues $\lambda_1, \lambda_2$ and orthonormal eigenvectors $u_1, u_2$ to form matrix $U$
    • Determine singular values $\sigma_1 = \sqrt{\lambda_1}, \sigma_2 = \sqrt{\lambda_2}$ to form matrix $\Sigma$
    • Compute right singular vectors $v_i = \frac{1}{\sigma_i} A^T u_i$ and find orthonormal $v_3$ in null space of $A$ to form $V$
    • Express final result as $A = U \Sigma V^T$
12. 14 Marks
    Three samples, each of size 5, were drawn from three uncorrelated normal populations with equal variances. Test the hypothesis that the population means are equal at 5% Level.

    Sample 1	10	12	9	16	13
    Sample 2	9	7	12	11	11
    Sample 3	14	11	15	14	16

    How to answer

    • Set up null hypothesis $H_0: \mu_1 = \mu_2 = \mu_3$ vs alternative $H_1$
    • Calculate sample totals, total sum $T$, and Correction Factor $CF = T^2 / N$
    • Calculate Total Sum of Squares (SST) and Between-Sample Sum of Squares (SSC)
    • Calculate Within-Sample Sum of Squares (SSE = SST - SSC)
    • Construct ANOVA table to find $F$-ratio
    • Compare calculated $F$ with critical value $F_{0.05}(2, 12)$ and state conclusion