AI/AL/CD-401 (GS) – Introduction to Discrete Structure and Linear Algebra

Let 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² - b²| is a multiple of 5. Prove that R is reflexive, symmetric, but not transitive.

Consider a set C = {1, 2, 3, 4, 5, 6, 8, 10, 12, 15} ordered by divisibility. Draw its Hasse diagram.

Consider two sets A and B. Let A = {2, 3, 4, 5} and B = {4, 5, 6, 7}. Using Venn diagrams, prove: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'.

Given the recurrence relation aₙ = aₙ₋₁ + 4aₙ₋₂ with initial conditions a₀ = 2 and a₁ = 5, determine the closed-form expression for the sequence.

Show that the set H = {e, a, a², a³} is a subgroup of a group G where G = {e, a, a², a³, b, ab, a²b, a³b}.

Let (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).

Let 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.

Find a route with the least total airfare that visits each of the cities in the given graph, where the weight on an edge is the least price available for a flight between the two cities.

Find a shortest route in distance between Newark and Camden, and between Newark and Cape May, using the given roads (New Jersey graph).

Find a least expensive route in terms of total tolls using the roads in the graph between the pairs of cities in part (A).

Calculate the gradient of the function f(X) = Tr(Xᵀ X) where X is a matrix.

Write a short note on Cholesky Decomposition.

Define Hypothesis. Write a short note on Null Hypothesis and Alternative Hypothesis.

Suppose 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 α = 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?

Write short note on any two: a) Recurrence Relation b) Tautologies and Contradiction c) Time Series Analysis