AL-401 Introduction to Discrete Structure & Linear Algebra - Jun 2026 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
   aExplain Equivalence relation with suitable example.
   How to answer

   • Define equivalence relation: reflexive, symmetric, transitive on a set
   • Explain each property with notation
   • Give suitable example e.g. congruence modulo n or equality
   • Verify all three properties for the example
2. 7 Marks
   bWrite a short note on Hasse diagram and Lattice.
   How to answer

   • Define partially ordered set and Hasse diagram representation
   • Explain construction rules of Hasse diagram with example
   • Define lattice as poset with meet and join
   • Give example of lattice vs non-lattice
3. 7 Marks
   aConsider two sets A and B. Let $A=\{1,3,5,6,8\}$ and $B=\{5,6,7,8,9\}$, using Venn diagrams prove the following statements:

   1. (i))Prove that $(A \cup B)' = A' \cap B'$
   2. (ii))Prove that $(A \cap B)' = A' \cup B'$
   How to answer

   • State given sets A={1,3,5,6,8}, B={5,6,7,8,9} and De Morgan's laws
   • Draw Venn diagrams for LHS and RHS of (i)
   • Draw Venn diagrams for LHS and RHS of (ii)
   • Conclude equality from diagrams
4. 7 Marks
   bSolve the recurrence relation $a_n = 2a_{n-1} + 3a_{n-2}$, given the initial condition $a_0 = 5$ and $a_1 = 10$.
   How to answer

   • Form characteristic equation $r^2 = 2r+3$
   • Find roots r=3, -1 and write homogeneous solution
   • Use $a_0=5, a_1=10$ to find constants
   • Write closed-form $a_n$ and verify
5. 7 Marks
   aLet $X = \{0,1,2,3,4,5,6,7\}$ with addition modulo 8. Is X a group? Justify your answer.
   How to answer

   • State group axioms: closure, associativity, identity, inverse
   • Check closure and associativity for addition modulo 8
   • Identify identity 0 and inverses
   • Conclude X is group (abelian group $Z_8$)
6. 7 Marks
   bConstruct a truth table to verify whether the following compound proposition is a tautology, a contradiction, or a contingency: $\neg(p \to q) \leftrightarrow (p \wedge \neg q)$
   How to answer

   • List all 4 truth assignments for p,q
   • Compute $p \to q$, $\neg(p \to q)$, $p \wedge \neg q$
   • Compare columns for equivalence $\leftrightarrow$
   • Classify as tautology / contradiction / contingency
7. 7 Marks
   aExplain types of relation with suitable example.
   How to answer

   • Define relation and list types: reflexive, symmetric, transitive, etc.
   • Explain each type with condition
   • Give suitable example for each type
   • Mention equivalence, partial order as special cases
8. 7 Marks
   bDefine Ring and Field with its properties.
   How to answer

   • Define ring with two binary operations and axioms
   • Define field with additional multiplicative inverse axiom
   • List properties of each
   • Give examples e.g. Z as ring, Q as field
9. 7 Marks
   aFind the determinant and trace of the matrix $$A = \begin{bmatrix} -9 & 2 & 6 \\ 5 & 0 & -3 \\ -16 & 4 & 11 \end{bmatrix}$$
   How to answer

   • Use formula trace = sum of diagonal elements
   • Compute determinant by expansion / rule
   • Simplify to numerical values
   • State determinant and trace
10. 7 Marks
    bDefine a bipartite graph. Prove that a simple graph G is bipartite if and only if it contains no odd cycles.
    How to answer

    • Define bipartite graph with partition V1, V2
    • Prove necessity: bipartite implies no odd cycle
    • Prove sufficiency: no odd cycle implies 2-colorable / bipartite
    • Conclude equivalence
11. 7 Marks
    aWhat is Test of hypothesis? Write concept and formulation.
    How to answer

    • Define null and alternative hypothesis
    • Explain concept: significance, test statistic, p-value
    • Describe formulation steps
    • Give example of formulation
12. 7 Marks
    bUsing Cholesky decomposition, verify that whether the following matrix is positive defined or not $$A = \begin{bmatrix} -2 & 1 & 1 \\ -11 & 4 & 5 \\ -1 & 1 & 0 \end{bmatrix}$$
    How to answer

    • State Cholesky condition $A = LL^T$ with positive pivots
    • Attempt decomposition / check leading principal minors
    • Show failure due to negative diagonal / non-positive pivot
    • Conclude not positive definite
13. 7 Marks
    aWrite a short note on Eigen Decomposition.
    How to answer

    • Define eigen decomposition $A = Q\Lambda Q^{-1}$
    • Explain eigenvalues, eigenvectors and diagonalization condition
    • Mention applications
    • Give small example
14. 7 Marks
    bLet $G = \{1,2,3,4,5,6\}$. Show that G forms an abelian group under the operation of multiplication modulo $7(X_7)$. Find the inverse of each element.
    How to answer

    • Verify closure, associativity, identity 1 under $\times_7$
    • Show commutativity for abelian property
    • Find inverse of each element 1 to 6
    • Conclude G is abelian group
15. 14 Marks
    Write a short note on any **two** of the following:

    1. (i))Time Series Analysis
    2. (ii))ANOVA
    3. (iii))Type-II Error
    How to answer

    • Select any two topics from the three options
    • Define each with key terms and formula / steps
    • Give example / application
    • Write concise concluding remark