AL-401 Introduction to Discrete Structure and Linear Algebra - Dec 2024 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
   aLet $A$ be the set of even numbers between 10 and 20, and $B$ be the set of multiples of 5 between 15 and 35. If $a$ is an even number from set $A$, and $b$ is a multiple of 5 from set $B$, find the set of ordered pairs, such that '$a$' is a factor of '$b$' and $a$ is less than $b$.
   How to answer

   • Define set A = {12, 14, 16, 18}
   • Define set B = {20, 25, 30}
   • Check conditions for each pair (a, b) where a | b and a < b
   • List valid ordered pairs, e.g., (12 does not divide 20, 25, 30; etc.)
2. 7 Marks
   bConsider the relation $R$ on the set of integers $\mathbb{Z}$ defined by $aRb$ if and only if $a^2 - b^2$ is divisible by 4. Determine the common relations on $\mathbb{Z}$ that are the transitive closures of $R$.
   How to answer

   • Analyze condition a^2 = b^2 (mod 4)
   • Show parity dependence: even numbers squared are 0 mod 4, odd numbers squared are 1 mod 4
   • Determine if R is already transitive (equivalence relation)
   • State the transitive closure and the resulting equivalence classes
3. 7 Marks
   aSuppose that the relation $R$ is irreflexive. Is $R^2$ necessarily irreflexive? Give a reason for your answer.
   How to answer

   • Define an irreflexive relation (no (a, a) in R)
   • Define composition R^2 = R o R
   • Provide a counterexample: e.g., set {1, 2}, R = {(1, 2), (2, 1)}, which is irreflexive
   • Show that R^2 contains (1, 1) and (2, 2), hence R^2 is not irreflexive
   • Conclude that R^2 is not necessarily irreflexive
4. 7 Marks
   bSolve the recurrence relation $a_n = a_{n-1} + 6a_{n-2}$ given the initial conditions $a_0 = 3$ and $a_1 = 6$.
   How to answer

   • Write characteristic equation: r^2 - r - 6 = 0
   • Find roots: (r - 3)(r + 2) = 0 => r_1 = 3, r_2 = -2
   • Form general solution: a_n = A(3)^n + B(-2)^n
   • Apply initial conditions: A + B = 3 and 3A - 2B = 6
   • Solve for constants: A = 12/5, B = 3/5
   • Write final closed-form expression for a_n
5. 7 Marks
   aProve that a subgroup $H$ of a group $G$ is normal if and only if $xHx^{-1} = H, \forall x \in G$.
   How to answer

   • State standard definition of normal subgroup (left coset = right coset, xH = Hx)
   • Prove 'if' direction: Assume xHx^{-1} = H, multiply both sides by x to get xH = Hx
   • Prove 'only if' direction: Assume xH = Hx, multiply by x^{-1} on right to get xHx^{-1} = H
   • Show inclusion in both directions: xHx^{-1} \subseteq H and H \subseteq xHx^{-1}
6. 7 Marks
   bLet $G = \{0, 1, 2, 3, 4, 5\}$ with addition modulo 6. Is $G$ a group? Justify your answer.
   How to answer

   • Construct the Cayley table (addition table modulo 6)
   • Verify Closure property: (a + b) mod 6 belongs to G
   • Verify Associativity: (a + (b + c)) mod 6 = ((a + b) + c) mod 6
   • Identify Identity element: 0, since (a + 0) mod 6 = a
   • Find Inverses for each element: 0^{-1}=0, 1^{-1}=5, 2^{-1}=4, 3^{-1}=3, 4^{-1}=2, 5^{-1}=1
   • Conclude that (G, +_6) is a group (specifically a cyclic group of order 6)
7. 7 Marks
   aConstruct a niche overlap graph for six species of birds, where the hermit thrush competes with the robin and with the blue jay, the robin also competes with the mockingbird, the mockingbird also competes with the blue jay, and the nuthatch competes with the hairy wood-pecker.
   How to answer

   • Define vertices: Hermit Thrush (HT), Robin (R), Blue Jay (BJ), Mockingbird (MB), Nuthatch (NH), Hairy Woodpecker (HW)
   • Identify edges representing competition: (HT, R), (HT, BJ), (R, MB), (MB, BJ), (NH, HW)
   • Draw an undirected graph with the 6 vertices and 5 edges
   • Note the two disconnected components: {HT, R, BJ, MB} and {NH, HW}
8. 7 Marks
   bLet $p$ and $q$ be the propositions $p$ : It is below freezing. $q$ : It is snowing. Write these propositions using $p$ and $q$ and logical connectives (including negations). i) It is below freezing and snowing. ii) It is below freezing but not snowing. iii) It is not below freezing and it is not snowing. iv) It is either snowing or below freezing (or both). v) If it is below freezing, it is also snowing. vi) Either it is below freezing or it is snowing, but it is not snowing if it is below freezing. vii) That it is below freezing is necessary and sufficient for it to be snowing.
   How to answer

   • i) p ∧ q
   • ii) p ∧ ¬q
   • iii) ¬p ∧ ¬q
   • iv) q ∨ p
   • v) p → q
   • vi) (p ∨ q) ∧ (p → ¬q)
   • vii) p ↔ q
9. 7 Marks
   aFind a route with the least total airfare that visits each of the cities in this graph, where the weight on an edge is the least price available for a flight between the two cities.

   

   How to answer

   • Identify the 5 cities: San Francisco, Los Angeles, Denver, Detroit, New York
   • Formulate as TSP (Traveling Salesperson Problem)
   • Evaluate candidate tours visiting all 5 cities
   • Calculate costs: e.g., SF - LA ($69) - Denver ($209) - NY ($279) - Detroit ($189) - SF ($329) or SF - LA ($69) - Detroit ($349) ...
   • Identify the tour with minimum cost and state the total airfare
10. 7 Marks
    bGiven a matrix $F$ with SVD $F = U \Sigma V^T$, where: $$U = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \Sigma = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}, V = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$ Find the original matrix $F$.
    How to answer

    • Find V^T: Since V is identity, V^T = [[1, 0], [0, 1]]
    • Compute Sigma * V^T = [[2, 0], [0, 3]] * [[1, 0], [0, 1]] = [[2, 0], [0, 3]]
    • Compute F = U * (Sigma * V^T) = [[1, 0], [0, 1]] * [[2, 0], [0, 3]] = [[2, 0], [0, 3]]
    • Conclude that F = [[2, 0], [0, 3]]
11. 7 Marks
    aFind the Determinant and trace of the matrix: $$\begin{pmatrix} 2 & -1 & 0 \\ 3 & 4 & 2 \\ 1 & 0 & -3 \end{pmatrix}$$
    How to answer

    • Trace calculation: Trace(A) = 2 + 4 + (-3) = 3
    • Determinant expansion along row 1:
    • det(A) = 2 * [4*(-3) - 2*0] - (-1) * [3*(-3) - 2*1] + 0 = 2*(-12) + 1*(-9 - 2) = -24 - 11 = -35
    • State final answers: Trace = 3, Determinant = -35
12. 7 Marks
    bUsing Cholesky decomposition, Verify that whether the following matrix is positive definite or not.
    How to answer

    • Note: The specific matrix for this part is omitted in the printed question (or references 6(a))
    • State the definition of Cholesky decomposition: A = L * L^T where L is lower triangular with positive diagonal elements
    • Show steps to compute L elements: l_{jj} = sqrt(a_{jj} - sum_{k=1}^{j-1} l_{jk}^2)
    • Conclude that if all diagonal entries of L are real and positive, matrix is positive definite
13. 7 Marks
    aWrite a detail note on Analysis of Variance.
    How to answer

    • Define ANOVA and its purpose (comparing means of three or more groups)
    • State basic assumptions (normality, independence, homogeneity of variances)
    • Explain One-Way vs Two-Way ANOVA
    • Provide formulas for Total Sum of Squares (SST), Between-group SS (SSB), and Within-group SS (SSW)
    • Present the standard ANOVA table (Source, SS, df, MS, F-ratio)
14. 7 Marks
    bA sample of 100 B.Sc. Student is taken from a medical college with height having standard deviation (S.D. = 10 cm). The mean height of sample of student is found 168.8 cm. Can we accept that the mean height of student is 170 cm. Justify your answer.
    How to answer

    • Set up null hypothesis H_0: mu = 170 cm and alternative H_1: mu != 170 cm (two-tailed)
    • Compute standard error: SE = s / sqrt(n) = 10 / sqrt(100) = 1.0
    • Calculate test statistic: z = (168.8 - 170) / 1.0 = -1.2
    • Find critical value at 5% level of significance: z_critical = 1.96
    • Compare: |z| = 1.2 < 1.96, so accept null hypothesis H_0
    • Conclude that it can be accepted that the mean height of students is 170 cm
15. 14 Marks
    Write short note on any two: a) Type-I and Type-II Errors b) Eigen decomposition c) Abelian group and cyclic group
    How to answer

    • a) Type-I Error: rejecting H_0 when true (alpha); Type-II Error: failing to reject H_0 when false (beta); decision table
    • b) Eigen decomposition: Factorization of diagonalizable matrix A = Q Lambda Q^{-1}; eigenvalues and eigenvectors
    • c) Abelian group: group satisfying commutative law (ab = ba); Cyclic group: group generated by a single element (G = <g>)