IIT M FOUNDATION DIPLOMA FN EXAM - 01 Sep 2024

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Key Concepts

A. Linear Programming (Optimization)

• Primal Problem Formulation:

  • Objective: Minimize/maximize a linear function (e.g., cost/profit).
  • Constraints: Linear inequalities (resource limits).
  • Non-negativity: Variables ≥ 0.

  • Example (Q2, Q3):

    Minimize: 2x + 3y
    Subject to:
      2x + y ≤ 90 (labor hours),
      x + 3y ≤ 80 (machine hours),
      x, y ≥ 0.

  • Solution Method: Graphical (for 2D) or Simplex algorithm.

• Dual Problem: Not directly tested here, but useful for sensitivity analysis.

B. Convex Sets & Functions

• Convex Set (Q4):

  • A set where the line segment joining any two points lies entirely within the set.

  • Examples:

    • Semicircle (Q4B), Triangle (Q4C).
    • Non-examples: "V" shape (Q4D), disjoint circles (Q4A).

• Convex Function (Q5):

  • A function where the line segment between any two points on the graph lies above the graph.

  • Tests:

    • Quadratic Forms: $f(v) = v^T A v$ is convex if matrix $A$ is positive semidefinite (e.g., Q5B, Q5D).
    • Hessian Matrix: For $f(x, y) = x^2 + y^2 + 3$, the Hessian is $\begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}$ (positive definite → convex).
    • Product of Convex Functions: Not necessarily convex (e.g., Q5A is not convex).

C. Probability & Statistics

• Chebyshev’s Inequality (Q7):

  • Bounds the probability of a random variable deviating from its mean.

  • Formula:

    P(|X - μ| ≥ kσ) ≤ 1/k²

  • Example: For $μ = 70$, $σ = 8$, $k = 2$:

    P(|X - 70| ≥ 16) ≤ 1/4 = 0.25.

• Normal Distribution (Q9):

  • Linear combinations of independent normals are normal.

  • Example: $U = 2X - 3Y$ where $X \sim N(-1, 11)$, $Y \sim N(1, 9)$.

    • $U \sim N(μ_U, σ_U²)$, where:

      μ_U = 2μ_X - 3μ_Y = 2(-1) - 3(1) = -5,
      σ_U² = 4Var(X) + 9Var(Y) = 4(11) + 9(9) = 127.

    • Standardize to $Z$: $P(U > 2) = P(Z > (2 - (-5))/√127) ≈ P(Z > 0.62) ≈ 0.2656$.

• Joint & Conditional Distributions (Q13, Q14):

  • Joint PDF: $f(x, y) = 18x²y²$ for $x, y ≥ 0$, $x + y ≤ 1$.

  • Conditional PDF (Q13):

    f_{X|Y}(x|y) = f(x, y)/f_Y(y),

    where $f_Y(y) = \int_0^{1-y} 18x²y² dx = 6y²(1 - y)³$.

    • Result: $f_{X|Y}(x|y) = 3x²/(1 - y)³$ for $0 < x < 1 - y$.

  • Conditional Probability (Q14):

    P(X < 0.5 | Y = 0.5) = \int_0^{0.5} f_{X|Y}(x|0.5) dx = 1.

D. Linear Algebra

• Eigenvalues & Diagonalizability (Q10):

  • Trace = Sum of eigenvalues = 3.
  • Determinant = Product of eigenvalues = 2.

  • Given eigenvalue $λ_1 = 1$, let $λ_2 = a + bi$, $λ_3 = a - bi$.

    • Then: $1 + 2a = 3$ → $a = 1$.
    • $1 \cdot (a² + b²) = 2$ → $b² = 1$ → $b = ±1$.
    • Possible eigenvalues: $1, 1 + i, 1 - i$ (Q10C).
  • Diagonalizable: Yes, if eigenvalues are distinct or matrix is symmetric (not necessarily symmetric/Hermitian here, but diagonalizable due to distinct eigenvalues).

• Nullspace (Q15):

  • For matrix $A$, solve $A \mathbf{x} = \mathbf{0}$.
  • Example: $A$ in Q15 has nullspace spanned by $\begin{pmatrix} 1 \\ -2 \\ 1 \end{pmatrix}$.

E. Optimization in Geometry

• Maximizing Area with Constraints (Q6):

  • Problem: Fence 3 sides of a rectangle with 120m (river on 4th side).

  • Solution:

    • Let sides be $x$ (parallel to river) and $y$ (perpendicular).
    • Constraint: $x + 2y = 120$.
    • Area: $A = xy = y(120 - 2y)$.

    • Maximize by setting derivative $dA/dy = 0$:

      120 - 4y = 0 → y = 30, x = 60.

    • Max Area: $60 \times 30 = 1800$ m².

F. Machine Learning Basics

• Linear Regression Loss (Q8):

  • Loss Function: Mean Squared Error (MSE):

    L = \frac{1}{n} \sum_{i=1}^n (f(\mathbf{x}^i) - y^i)².

  • Example: For $f(\mathbf{x}) = x_1 + 2x_2 + x_3$, compute predictions and compare to $y$.

• Principal Component Analysis (PCA) (Q12):

  • Goal: Project data onto lower-dimensional subspace to maximize variance (or minimize reconstruction error).

  • Steps:

    1. Center the data.
    2. Compute covariance matrix.
    3. Eigen decomposition to find principal components.

  • Key Points:

    • Reduces dimensionality (Q12C).
    • Maximizes variance of projection (Q12A).
    • Does not maximize reconstruction error (Q12D is false).

• Least Squares Minimization (Q11):

  • Problem: Minimize $g(p) = \sum \|p - x_i\|²$.

  • Solution: The minimizer $q$ is the mean of the data points.

    • For $q = \begin{pmatrix} 4 \\ 0 \\ 3 \end{pmatrix}$, the sum $\sum x_i = 10q = \begin{pmatrix} 40 \\ 0 \\ 30 \end{pmatrix}$.
    • Distance from origin: $\| \sum x_i \| = 50$ (Q11C).

2. Key Equations

Graph 2: Probability & Statistics

Graph 3: Machine Learning & Geometry

Graph 4: Convexity