Introduction to Discrete Structure &Linear Algebra (AL-401) - Important Questions

Draw the Hasse diagram of a finite set ordered by divisibility.

Using Venn diagrams, prove De Morgan's laws $(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$.

Write a short note on Hasse diagram and Lattice

Explain types of relations including reflexive, symmetric, transitive and equivalence with examples.

Explain the concept of an equivalence relation with a suitable example.

Given sets $A$ and $B$ with $a \in A$, $b \in B$, find the set of ordered pairs $(a,b)$ such that $a$ is a factor of $b$ and $a < b$.

Prove that a given relation $R$ is reflexive and symmetric but not transitive.

Explain types of relations including reflexive, symmetric, transitive and equivalence relations with examples.

Write short notes on any three of: POSET, normal forms, gradient of a matrix, rings and fields.

Define Venn diagram and draw Venn diagrams for $A \cap (B-C)$ and $(A \cap B) \cup (A \cap C)$.

Using Venn diagrams, prove De Morgan's laws $(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$.

Determine the transitive closure of the relation $aRb$ iff $a^2-b^2$ is divisible by $4$ on $\mathbb{Z}$.

Solve second-order linear homogeneous recurrence $a_n = p a_{n-1} + q a_{n-2}$ with given $a_0, a_1$ to find closed-form expression.

Verify that $\mathbb{Z}_n$ with addition modulo $n$ is a group.

Prove that a given finite set (e.g. $\{-1,1,i,-i\}$ or $\{1,2,3,4,5,6\}$ under multiplication modulo $7$) is an abelian group under multiplication and find inverses.

Define ring and field with their properties.

Solve the second-order linear homogeneous recurrence $a_n = p a_{n-1} + q a_{n-2}$ with given $a_0, a_1$ to obtain closed form.

Show that a given finite set forms an abelian group under multiplication (or multiplication modulo $n$) and determine inverses.

Find all subgroups of the given groups $(Z_{12},+_{12})$ and $(Z_7^*,\times_7)$.

Check whether the set $\{0,1,\dots,n-1\}$ with addition modulo $n$ is a group and justify.

Write short note on recurrence relation (with tautologies/contradiction/time series options).

Prove that a subgroup $H$ of a group $G$ is normal if and only if $xHx^{-1} = H, \forall x \in G$.

Show that a given subset $H$ is a subgroup of a given group $G$.

In a semigroup, prove that if $a*c=c*a$ and $b*c=c*b$ then $(a*b)*c = c*(a*b)$.

Construct a truth table to prove/classify whether a given compound proposition is a tautology, contradiction, or contingency.

Define a bipartite graph and prove that a simple graph is bipartite if and only if it contains no odd cycles.

Find a minimum-cost route that visits each city exactly once (traveling salesperson problem) given airfares as edge weights.

Define compound proposition and explain different logical operations on propositions with truth tables.

Prove $(P \lor Q) \land (\neg P \land (\neg P \land Q)) \Leftrightarrow (\neg P \land Q)$.

Define a graph and describe various ways of representing graphs.

What is the coloring problem and define coloring of a graph?

Find a shortest / least-cost path between specified cities in a road network using given edge weights (distance or tolls).

Construct a niche overlap graph for the given competing bird species.

Translate English statements about freezing and snowing into symbolic form using $p$, $q$ and logical connectives.

Construct a truth table to determine whether a given compound proposition is a tautology, a contradiction, or a contingency.

Prove that in any graph the number of vertices of odd degree is even.

Find the determinant and trace of a given $3\times 3$ matrix.

Using Cholesky decomposition, verify whether a given matrix is positive definite.

Write a short note on Eigen Decomposition.

Find the singular value decomposition (SVD) $A = U\Sigma V^T$ of a given matrix $A$.

Solve a system of linear equations using Cholesky decomposition.

Using 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$.

Find the determinant and trace of a given $3 \times 3$ numerical matrix.

Use Cholesky decomposition to verify whether a given matrix is positive definite.

Given the SVD components $U, \Sigma, V$, reconstruct the original matrix $F = U\Sigma V^T$.

Calculate the gradient of the function $f(X) = \text{Tr}(X^T X)$, where $X$ is a matrix.

Write a short note on Cholesky decomposition.

Concept of test of hypothesis, definition of hypothesis, and null vs alternative hypothesis

Write a short note on any two of: Time Series Analysis, ANOVA, Type-II Error.

Explain Type-I and Type-II errors.

Large-sample z-test for a single population mean with known population standard deviation: test whether sample mean differs from hypothesized mean.

Test equality of three population means using one-way ANOVA from three samples of size 5.

Explain the concept of hypothesis testing, including definition of hypothesis and null vs alternative hypothesis and formulation/procedure.

Write a detailed note on Analysis of Variance.

One-sample t-test for population mean greater than a hypothesized value using raw sample data (unknown variance, small sample): compute test statistic, P-value and conclusion.

What are the critical values for a two-tailed one-sample $z$ test at $\alpha = .05$?

Complete the one-way ANOVA table for effect of four fertilizers and test for significant difference.

Test for population proportion (binomial proportion) that a coin is unbiased given observed number of heads.