AL-401 Introduction to Discrete Structure and Linear Algebra - Jun 2025 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
   aDefine Venn diagram. Draw the Venn diagrams for each of these combinations of the sets A, B and C.

   1. i)$A \cap (B-C)$
   2. ii)$(A \cap B) \cup (A \cap C)$
   How to answer

   • Definition of Venn diagram as pictorial representation of sets using overlapping closed curves
   • Venn diagram for $A \cap (B-C)$ - shading common to A and B excluding C
   • Venn diagram for $(A \cap B) \cup (A \cap C)$ - shading overlaps of A with B and A with C
2. 7 Marks
   bExplain Reflexive, symmetric, Transitive, equivalence relations with example.
   How to answer

   • Definition of reflexive, symmetric, transitive relations
   • Definition of equivalence relation as reflexive + symmetric + transitive
   • Example for each type with small set
   • Verification of properties on examples
3. 7 Marks
   aLet $A = \{1, 2, 3, 4, 6, 8, 9, 12, 18, 24\}$ be ordered by divisibility. Draw Hasse diagram.
   How to answer

   • List divisibility pairs among set elements
   • Identify cover relations by removing transitive edges
   • Draw layered Hasse diagram with 1 at bottom
   • Label all elements 1,2,3,4,6,8,9,12,18,24
4. 7 Marks
   bProve that $G = \{-1, 1, i, -i\}$ is an abelian group under multiplication.
   How to answer

   • Verify closure of multiplication on $\{-1,1,i,-i\}$ via Cayley table
   • Verify associativity, identity $1$, inverses
   • Verify commutativity $ab=ba$ for all pairs
   • Conclude abelian group of order 4
5. 7 Marks
   aFind all the subgroups

   1. i)$(Z_{12}, +_{12})$
   2. ii)$(Z_7^*, \times_7)$
   How to answer

   • Recall subgroups correspond to divisors for cyclic $Z_{12}$
   • List all subgroups of $(Z_{12},+_{12})$
   • Find order and subgroups of $Z_7^*$ cyclic group of order 6
   • List subgroups of $(Z_7^*,\times_7)$
6. 7 Marks
   bSolve the recurrence relation $a_n = 2a_{n-1} + 3a_{n-2}$ for $n \ge 2$ where $a_0 = 2$ and $a_1 = 2$.
   How to answer

   • Form characteristic equation $r^2=2r+3$
   • Find roots $r=3,-1$ and homogeneous solution $a_n=A\cdot 3^n+B\cdot(-1)^n$
   • Use $a_0=2, a_1=2$ to solve for A,B
   • Write closed form solution
7. 7 Marks
   aDefine compound proposition. Explain different operations on propositions with truth tables.
   How to answer

   • Define compound proposition built from atomic propositions and connectives
   • Explain negation, conjunction, disjunction, implication, biconditional
   • Give truth table for each operation
   • Give example of compound proposition
8. 7 Marks
   bShow that $(P \vee Q) \wedge (\neg P \wedge (\neg P \wedge Q)) \Leftrightarrow (\neg P \wedge Q)$.
   How to answer

   • Simplify LHS using absorption / distributive laws
   • Construct truth table for both sides or use equivalences
   • Show LHS reduces to $(\neg P \wedge Q)$
   • Conclude logical equivalence
9. 7 Marks
   aWhat is a Graph? Write about various ways of representing graphs.
   How to answer

   • Define graph as pair $(V,E)$ of vertices and edges
   • Describe adjacency matrix representation
   • Describe adjacency list and incidence matrix
   • Compare space and use cases
10. 7 Marks
    bUsing properties of determinants, prove that $$\begin{vmatrix} a & b & c \\ a-b & b-c & c-a \\ b+c & c+a & a+b \end{vmatrix} = a^3 + b^3 + c^3 - 3abc.$$
    How to answer

    • Apply row/column operations $R2 \to R2+R1$ etc. preserving determinant properties
    • Factor common terms to get triangular or known form
    • Expand determinant to $a^3+b^3+c^3-3abc$
    • Cite properties used at each step
11. 14 Marks
    Find Single Value Decomposition of $A = \begin{bmatrix} 1 & -1 \\ -2 & 2 \\ 2 & 2 \end{bmatrix}$.
    How to answer

    • Compute $A^T A$ and its eigenvalues / singular values
    • Find orthonormal eigenvectors V and $\Sigma$
    • Compute $U$ from $Av_i/\sigma_i$ and complete basis
    • Write $A = U \Sigma V^T$
12. 4 Marks
    aExplain Type-I and Type-II errors.
    How to answer

    • Define null and alternative hypotheses context
    • Define Type-I error as rejecting true $H_0$
    • Define Type-II error as accepting false $H_0$
    • Give example with significance and power
13. 10 Marks
    bThree 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.

    

    How to answer

    • State $H_0$: equal population means vs $H_1$
    • Compute group means, grand mean, SSB, SSW and F-ratio (one-way ANOVA)
    • Compare F with critical $F_{2,12}$ at 5% level
    • Decide to accept/reject $H_0$
14. 14 Marks
    Write short note on (any three)

    1. a)POSET
    2. b)Normal forms
    3. c)Gradient of a matrix
    4. d)Ring and fields.
    How to answer

    • Define each term: POSET, normal forms, gradient, ring/field
    • Give properties / types with examples
    • Give relevant formulas or diagrams
    • Conclude with applications