AL-401 Introduction to Discrete Structure and Linear Algebra - Jun 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
   aIf $A = \{2, 4, 6, 9\}$ and $B = \{4, 6, 18, 27, 54\}$, $a \in A$, $b \in B$, find the set of ordered pairs such that '$a$' is factor of '$b$' and $a < b$.
   How to answer

   • Identify elements of set A and set B
   • Test conditions: $a \mid b$ and $a < b$ for all pairs $(a, b) \in A \times B$
   • List all valid ordered pairs: (2, 4), (2, 6), (2, 18), (2, 54), (6, 18), (6, 54), (9, 18), (9, 27), (9, 54)
2. 7 Marks
   bLet $R$ be the relation on the set $\mathbb{R}$ of all real numbers defined by $a \mathrel{R} b$ if and only if $|a - b| \le 1$. Then prove that $R$ is reflexive, symmetric, but not transitive.
   How to answer

   • Prove reflexivity: for any $a \in \mathbb{R}$, $|a - a| = 0 \le 1 \implies a \mathrel{R} a$
   • Prove symmetry: $a \mathrel{R} b \implies |a - b| \le 1 \implies |b - a| \le 1 \implies b \mathrel{R} a$
   • Disprove transitivity by counterexample: choose $a = 0, b = 1, c = 2$, showing $a \mathrel{R} b$ and $b \mathrel{R} c$, but $|a - c| = 2 > 1$, so $(a, c) \notin R$
3. 7 Marks
   aLet $A = \{1, 2, 3, 4, 5, 6\}$ and $a \mathrel{R} b$ if and only if $a$ is multiple of $b$. Find: i) Domain ii) Range, iii) Matrix of a relation, iv) Digraph of the relation $R$.
   How to answer

   • List all ordered pairs of relation $R$: $(1,1), (2,1), (2,2), (3,1), (3,3), (4,1), (4,2), (4,4), (5,1), (5,5), (6,1), (6,2), (6,3), (6,6)$
   • Determine Domain = $\{1, 2, 3, 4, 5, 6\}$ and Range = $\{1, 2, 3, 4, 5, 6\}$
   • Construct $6 \times 6$ adjacency relation matrix $M_R$
   • Draw directed graph (digraph) with 6 vertices and directed edges representing $(a, b)$
4. 7 Marks
   bWhat common relations on $\mathbb{Z}$ are the transitive closures of the following relations? i) $a \mathrel{S} b$ if and only if $a + 1 = b$. ii) $a \mathrel{R} b$ if and only if $a - b = 2$.
   How to answer

   • Define transitive closure $R^+$ as $\bigcup_{n=1}^\infty R^n$
   • For (i): $a + 1 = b$, repeated composition gives $b = a + k$ for $k \ge 1$, which is the strict 'less than' relation ($a < b$)
   • For (ii): $a - b = 2$, repeated composition yields $a - b = 2k$ for $k \ge 1$, which is $a > b$ and $a \equiv b \pmod 2$
5. 7 Marks
   ai) Prove that $p \wedge q \implies q \vee p$ is a Tautology. ii) Show that $(p \vee q) \wedge (\neg p) \wedge (\neg q)$ is a contradiction
   How to answer

   • For (i): Construct truth table for variables $p, q$, evaluate $p \wedge q$, $q \vee p$, and $(p \wedge q) \implies (q \vee p)$, showing all outputs are T
   • For (ii): Construct truth table or use De Morgan's laws: $\neg p \wedge \neg q \equiv \neg(p \vee q)$, hence $(p \vee q) \wedge \neg(p \vee q) \equiv \text{False}$
   • Conclude that (i) is a tautology and (ii) is a contradiction
6. 7 Marks
   bProve that in any graph $G$, even number of vertices is of odd degree.
   How to answer

   • State the Handshaking Lemma: $\sum_{v \in V} \deg(v) = 2|E|$
   • Split the summation into vertices of even degree ($V_{even}$) and odd degree ($V_{odd}$): $\sum_{v \in V_{even}} \deg(v) + \sum_{v \in V_{odd}} \deg(v) = 2|E|$
   • Note that $2|E|$ is even and $\sum_{v \in V_{even}} \deg(v)$ is even
   • Deduce that $\sum_{v \in V_{odd}} \deg(v)$ must be even
   • Conclude that the count of odd-degree vertices $|V_{odd}|$ must be even
7. 7 Marks
   aSolve the equations $$6x + 15y + 55z = 76,$$ $$15x + 55y + 225z = 295,$$ $$55x + 225y + 979z = 1259$$ Using Cholesky decomposition method.
   How to answer

   • Formulate coefficient matrix $A$ and vector $b$
   • Decompose $A = L L^T$, calculating elements of lower triangular matrix $L$
   • Solve $L y = b$ by forward substitution
   • Solve $L^T x = y$ by back substitution
   • State final solutions for $x$, $y$, and $z$
8. 7 Marks
   bFind singular value decomposition for $A = \begin{bmatrix} 1 & 0 & 1 \\ -1 & 1 & 0 \end{bmatrix}$.
   How to answer

   • Compute $A A^T = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$ and find its eigenvalues and normalized eigenvectors to construct $U$
   • Calculate singular values $\sigma_1 = \sqrt{3}$, $\sigma_2 = 1$ to form $\Sigma$
   • Compute corresponding right singular vectors $v_i = \frac{1}{\sigma_i} A^T u_i$ and find $v_3$ orthogonal to span to form $V$
   • Write the final SVD representation $A = U \Sigma V^T$
9. 7 Marks
   aTo test the hypothesis that eating fish makes one smarter, a random sample of 12 persons take a fish oil supplement for one year and then are given an IQ test. Here are the results: 116 111 101 120 99 94 106 115 107 101 110 92 Test using the following hypothesis, report the test statistic with the P-value, then summarize your conclusion. $H_0: \mu = 100$ $H_a: \mu > 100$
   How to answer

   • Compute sample mean $\bar{x}$ and sample standard deviation $s$
   • Calculate test statistic $t = \frac{\bar{x} - 100}{s / \sqrt{12}}$ with degrees of freedom $df = 11$
   • Determine the right-tailed P-value $P(T > t)$ using t-distribution table
   • Compare P-value with standard significance level (e.g., $\alpha = 0.05$)
   • State conclusion: reject or fail to reject $H_0$
10. 7 Marks
    bWhat are the critical values for a one-independent sample non directional (two-tailed) $z$ test at a .05 level of significance?
    How to answer

    • Divide $\alpha = 0.05$ by 2 for a two-tailed test: $\alpha/2 = 0.025$
    • Find $z$ value corresponding to cumulative probability $1 - 0.025 = 0.975$
    • State critical values: $z = \pm 1.96$
11. 7 Marks
    aLet $A = \{1, 2, 3, 4, 6, 8, 9, 12, 18, 24\}$ be ordered by divisibility. Draw Hasse diagram.
    How to answer

    • Determine the covering relation for divisibility on set $A$
    • Place 1 at the lowest level (minimal element)
    • Place primes {2, 3} at level 1; {4, 6, 9} at level 2; {8, 12, 18} at level 3; {24} at top level
    • Draw line segments between covering pairs without drawing arrows or transitive/reflexive edges
12. 7 Marks
    bLet $G$ be a planar graph with 10 vertices, 3 components and 9 edges. Find the number of regions in $G$.
    How to answer

    • State Euler's generalized formula for planar graphs with $k$ components: $v - e + r = 1 + k$ (or $v - e + r = k + 1$)
    • Substitute $v = 10$, $e = 9$, $k = 3$: $10 - 9 + r = 1 + 3$
    • Solve for $r$: $1 + r = 4 \implies r = 3$
13. 7 Marks
    aFind chromatic number of the following graph-

    

    How to answer

    • Identify vertices $V = \{a, b, c, d, e, f\}$ and the edge set from the given diagram
    • Find cliques and cycles in the graph to establish a lower bound on chromatic number
    • Assign colors to adjacent vertices such that no two adjacent vertices share the same color
    • Conclude with the minimum number of colors required (chromatic number $\chi(G)$)
14. 7 Marks
    bWrite short note on partially ordered sets and explain with suitable example.
    How to answer

    • Define a partially ordered set (poset) $(S, \le)$ as a set together with a binary relation that is reflexive, antisymmetric, and transitive
    • State and define the three properties: Reflexivity ($a \le a$), Antisymmetry ($a \le b \wedge b \le a \implies a = b$), Transitivity ($a \le b \wedge b \le c \implies a \le c$)
    • Give a standard example such as $(\mathbb{Z}^+, \mid)$ (divisibility) or $(\mathcal{P}(A), \subseteq)$ (subset inclusion) with brief verification
15. 14 Marks
    Write short Note on a) Hasse diagram b) Lattice c) Weighted Graph
    How to answer

    • a) Hasse diagram: graphical representation of finite poset omitting reflexive loops and transitive edges; draw a simple example
    • b) Lattice: a poset where every pair of elements has a unique least upper bound (LUB / join) and greatest lower bound (GLB / meet)
    • c) Weighted Graph: a graph $G = (V, E, w)$ where each edge is assigned a numerical weight; explain applications like shortest path problem