AL-401 Introduction to Discrete Structure and Linear Algebra - Jun 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 T be the set of positive integers less than 10 and let "R be the relation on T defined by aRb if and only if $|a^2 - b^2|$ is a multiple of 5". Prove that R is reflexive, symmetric, but not transitive.
   How to answer

   • Define set $T = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.
   • Show reflexive: $|a^2 - a^2| = 0$, which is a multiple of 5 for all $a \in T$.
   • Show symmetric: if $|a^2 - b^2|$ is a multiple of 5, $|b^2 - a^2| = |a^2 - b^2|$ is also a multiple of 5.
   • Show not transitive by providing a counterexample: e.g., check $a^2 \pmod 5$ values or specific elements showing $aRb$ and $bRc$ do not imply $aRc$ if any, or verify if the claim holds/fails based on quadratic residues modulo 5.
2. 7 Marks
   bConsider a set $C = \{1, 2, 3, 4, 5, 6, 8, 10, 12, 15\}$ ordered by divisibility. Draw its Hasse diagram.
   How to answer

   • List all elements and their covering relations under divisibility.
   • Bottom element is 1.
   • Level 1: Prime elements 2, 3, 5.
   • Higher levels: 4, 6, 10, 15, and top elements 8, 12.
   • Draw vertices and edges indicating transitive reduction without redundant edges or reflexive loops.
3. 7 Marks
   aConsider two sets A and B. Let $A = \{2, 3, 4, 5\}$ and $B = \{4, 5, 6, 7\}$. Using Venn diagrams, prove the following statements: Prove that $(A \cup B)' = A' \cap B'$. Prove that $(A \cap B)' = A' \cup B'$.
   How to answer

   • Define universal set $U$ containing elements of $A$ and $B$.
   • Draw Venn diagrams illustrating $A \cup B$ and its complement $(A \cup B)'$.
   • Draw Venn diagrams showing $A'$, $B'$, and their intersection $A' \cap B'$; show equality.
   • Draw Venn diagrams illustrating $A \cap B$ and its complement $(A \cap B)'$.
   • Draw Venn diagrams showing $A' \cup B'$ and show regions are identical.
4. 7 Marks
   bGiven the recurrence relation $a_n = a_{n-1} + 4a_{n-2}$ with initial conditions $a_0 = 2$ and $a_1 = 5$, determine the closed-form expression for the sequence.
   How to answer

   • Write characteristic equation: $r^2 - r - 4 = 0$.
   • Find characteristic roots: $r = \frac{1 \pm \sqrt{17}}{2}$.
   • Write general solution: $a_n = c_1 \left(\frac{1 + \sqrt{17}}{2}\right)^n + c_2 \left(\frac{1 - \sqrt{17}}{2}\right)^n$.
   • Apply initial conditions: $a_0 = 2 \implies c_1 + c_2 = 2$.
   • Use $a_1 = 5$ to solve for constants $c_1$ and $c_2$.
   • Substitute constants back into the general solution to obtain the closed-form expression.
5. 7 Marks
   aShow that the set $H = \{e, a, a^2, a^3\}$ is a subgroup of a group $G$ where $G = \{e, a, a^2, a^3, b, ab, a^2b, a^3b\}$.
   How to answer

   • State subgroup criteria (finite subgroup test or closure and inverse).
   • Show closure: For any $a^i, a^j \in H$, $a^i \cdot a^j = a^{(i+j) \pmod 4} \in H$ since $a^4 = e$.
   • Show identity: $e \in H$.
   • Show inverse: Inverse of $a$ is $a^3 \in H$, inverse of $a^2$ is $a^2 \in H$, inverse of $e$ is $e \in H$.
   • Conclude $H$ is a subgroup of $G$ (in fact, a cyclic subgroup generated by $a$).
6. 7 Marks
   bLet $(A, *)$ be a semigroup. Show that, for $a, b, c$ in $A$, if $a * c = c * a$ and $b * c = c * b$, then $(a * b) * c = c * (a * b)$.
   How to answer

   • Start with left-hand side: $(a * b) * c$.
   • Apply associativity: $(a * b) * c = a * (b * c)$.
   • Substitute given commutativity $b * c = c * b$: $= a * (c * b)$.
   • Apply associativity: $= (a * c) * b$.
   • Substitute given commutativity $a * c = c * a$: $= (c * a) * b$.
   • Apply associativity: $= c * (a * b)$, proving the statement.
7. 7 Marks
   aLet G be a simple graph. Show that the relation R on the set of vertices of G such that $uRv$ if and only if there is an edge associated to $\{u, v\}$ is a symmetric, irreflexive relation on G.
   How to answer

   • Define simple graph: contains no self-loops and no parallel edges, edges are unordered pairs $\{u, v\}$.
   • Show irreflexivity: A simple graph has no self-loops, so for any vertex $u$, there is no edge $\{u, u\}$. Hence $(u, u) \notin R$, so $R$ is irreflexive.
   • Show symmetry: Edges are undirected, so the edge $\{u, v\}$ is identical to $\{v, u\}$. Therefore $uRv \implies vRu$, making $R$ symmetric.
8. 7 Marks
   bFind 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 vertices: Jammu, Mumbai, Surat, Jaipur, Chandigarh.
   • List all possible Hamiltonian circuits starting from a fixed vertex (e.g., Jammu).
   • Calculate the sum of airfares for each possible cycle.
   • Compare total costs of the circuits.
   • State the optimal sequence of cities and the minimum total airfare.
9. 7 Marks
   aThe weighted graphs in the figures here show some major roads in New Jersey. Part (A) shows the distances between cities on these roads; Part (B) shows the tolls. Find a shortest route in distance between Newark and Camden, and between Newark and Cape May, using these roads.

   

   How to answer

   • Apply Dijkstra's algorithm or inspection on Graph (A) starting from Newark.
   • Determine paths to Camden: Newark -> Woodbridge -> Trenton -> Camden (20 + 42 + 30 = 92) vs Newark -> Woodbridge -> Camden (20 + 60 = 80) vs Newark -> Woodbridge -> Asbury Park -> Camden (20 + 35 + 40 = 95). Shortest to Camden is via Woodbridge (distance = 80).
   • Determine paths to Cape May from Newark via Camden or Atlantic City.
   • Calculate total minimum distance and state the full shortest routes.
10. 7 Marks
    bFind a least expensive route in terms of total tolls using the roads in the graph between the pairs of cities in part (A).
    How to answer

    • Consider Graph (B) edge weights representing tolls.
    • Find minimum toll route from Newark to Camden: calculate Newark -> Woodbridge ($0.60) -> Camden ($0.00) = $0.60.
    • Find minimum toll route from Newark to Cape May: evaluate routes continuing from Camden (e.g., Camden -> Atlantic City ($0.00) -> Cape May ($0.75), total toll = $0.60 + $0.00 + $0.75 = $1.35).
    • State the optimal least-toll routes and their total toll values.
11. 7 Marks
    aCalculate the gradient of the function $f(X) = \text{Tr}(X^T X)$, where $X$ is a matrix.
    How to answer

    • Express the trace function in component form: $f(X) = \text{Tr}(X^T X) = \sum_{i} (X^T X)_{ii} = \sum_{i} \sum_{j} X_{ji} X_{ji} = \sum_{i,j} X_{ij}^2$.
    • Compute partial derivative with respect to an arbitrary element $X_{ij}$: $\frac{\partial f}{\partial X_{ij}} = 2X_{ij}$.
    • Combine the scalar partial derivatives into matrix form: $\nabla_X f(X) = \left[\frac{\partial f}{\partial X_{ij}}\right] = 2X$.
    • Alternatively, use differential notation: $d(\text{Tr}(X^T X)) = \text{Tr}(d(X^T) X + X^T dX) = 2\text{Tr}(X^T dX) \implies \nabla_X f(X) = 2X$.
12. 7 Marks
    bWrite a short note on Cholesky Decomposition.
    How to answer

    • Define Cholesky decomposition: Factorization of a Hermitian/symmetric positive-definite matrix $A$ into $A = L L^T$ (or $L L^*$), where $L$ is a lower triangular matrix with real and positive diagonal entries.
    • State necessary and sufficient condition: $A$ must be symmetric (or Hermitian) and positive definite.
    • Provide algorithmic formula for elements: $L_{jj} = \sqrt{A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2}$ and $L_{ij} = \frac{1}{L_{jj}} \left(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}\right)$.
    • List applications: Solving linear systems, Monte Carlo simulations, Kalman filters, optimization.
13. 7 Marks
    aDefine Hypothesis. Write a short note on Null Hypothesis and Alternative Hypothesis.
    How to answer

    • Define statistical hypothesis: An assumption or proposition about a population parameter.
    • Define Null Hypothesis ($H_0$): A statement of no effect, no difference, or status quo to be tested for possible rejection.
    • Define Alternative Hypothesis ($H_1$ or $H_a$): The claim that contradicts $H_0$, indicating existence of an effect or difference.
    • Briefly contrast their roles in decision making and error types (Type I and Type II).
14. 7 Marks
    bSuppose the average salary of a principal in a college in the private sector is Rs. 45,000 per month, and a sample of 50 principals has a mean of Rs. 48,326 with a significance level of $\alpha = 0.05$. Can we claim that principals earn Rs. 45,000 per month, given that the standard deviation of the population is Rs. 1,523?
    How to answer

    • Set up hypotheses: $H_0: \mu = 45000$ vs $H_1: \mu \neq 45000$.
    • Compute test statistic: $z = \frac{48326 - 45000}{1523 / \sqrt{50}} = \frac{3326}{215.38} \approx 15.44$.
    • State critical value for two-tailed test at $\alpha = 0.05$: $z_{critical} = \pm 1.96$.
    • Compare: $|z| = 15.44 > 1.96$, so reject $H_0$.
    • Conclusion: Reject the null hypothesis; we cannot claim that principals earn Rs. 45,000 per month.
15. 14 Marks
    Write short note on any two: a) Recurrence Relation b) Tautologies and Contradiction c) Time Series Analysis
    How to answer

    • For (a) Recurrence Relation: Definition, homogeneous vs non-homogeneous, degree, examples (Fibonacci relation).
    • For (b) Tautologies and Contradiction: Definition of tautology (always true) and contradiction (always false), truth tables and simple propositional examples.
    • For (c) Time Series Analysis: Definition of time series, four components (trend, seasonal, cyclical, irregular variations), applications in forecasting.