IIT M FOUNDATION DIPLOMA AN 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 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):

    \text{Minimize } 4x + 3y
    \text{Subject to: }
    2x + y \leq 80, \quad x + 3y \leq 90, \quad x, y \geq 0

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

• Dual Problem: Not directly tested here but related to constraints.

B. Convex Sets & Functions

• Convex Set (Q4):

  • A set $S$ is convex if for any $x, y \in S$, the line segment joining $x$ and $y$ lies entirely in $S$.

  • Examples:

    • Triangular region with vertices $(0,0), (1,0), (0,1)$ (convex).
    • Region between $y = 4x^2$ and $y = 2x + 5$ (non-convex unless specified otherwise).
  • Epipgraph: Set of points above a function’s graph. Convex if the function is convex.

• Convex Function (Q5):

  • A function $f$ is convex if:

    f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y) \quad \forall \lambda \in [0,1]

  • Tests:

    • Hessian Matrix: For $f(v) = v^T A v$, $f$ is convex if $A$ is positive semidefinite.

      • Example (Q5B): $A = \begin{bmatrix} -2 & -1 \\ -1 & 1 \end{bmatrix}$ is not convex (eigenvalues: $-2.62, 1.62$).
      • Example (Q5C): $f(x,y) = x^2 + y^2 + 3$ is convex (Hessian is $2I$).
    • Quadratic Forms: Check eigenvalues of $A$.

C. Calculus-Based Optimization

• Unconstrained Optimization (Q6):

  • Problem: Maximize area $A = xy$ given perimeter constraint $2x + y = 200$ (fencing problem).

  • Steps:

    1. Express $y$ in terms of $x$: $y = 200 - 2x$.
    2. Substitute into $A$: $A(x) = x(200 - 2x) = 200x - 2x^2$.
    3. Find critical point: $A'(x) = 200 - 4x = 0 \Rightarrow x = 50$.
    4. Evaluate $A(50) = 50 \times 100 = 5000$.

• Chebyshev’s Inequality (Q7):

  • Bounds probability of deviation from the mean:

    P(|X - \mu| \geq k\sigma) \leq \frac{1}{k^2}

  • Example: For $\mu = 70$, $\sigma = 8$, $k = 3$:

    P(|X - 70| \geq 24) \leq \frac{1}{9} \approx 0.11

D. Probability & Statistics

• Linear Regression Loss (Q8):

  • Loss Function (MSE):

    L = \frac{1}{n} \sum_{i=1}^n (f(x_i) - y_i)^2

  • Example: For $f(x) = x_1 + 3x_2 - x_3$, compute $L$ for given data points.

• Normal Distribution & Linear Combinations (Q9):

  • If $X \sim N(\mu_X, \sigma_X^2)$ and $Y \sim N(\mu_Y, \sigma_Y^2)$, then:

    U = aX + bY \sim N(a\mu_X + b\mu_Y, a^2\sigma_X^2 + b^2\sigma_Y^2)

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

    U \sim N(2(-1) - 3(1), 4(11) + 9(9)) = N(-5, 127)

    Standardize to find $P(U < 2)$:

    P\left(Z < \frac{2 - (-5)}{\sqrt{127}}\right) \approx P(Z < 0.62) = 0.7343

• Joint & Conditional Distributions (Q13, Q14):

  • Joint PDF: $f(x,y) = 18x^2y^2$ for $x, y \geq 0, x + y \leq 1$.

  • Conditional PDF:

    f_{X|Y}(x|y) = \frac{f(x,y)}{f_Y(y)} = \frac{18x^2y^2}{\int_0^{1-y} 18x^2y^2 dx} = \frac{3x^2}{(1-y)^3}

  • Conditional Probability:

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

E. Linear Algebra

• Eigenvalues & Diagonalization (Q10):

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

  • Given eigenvalue $\lambda_1 = 1$, let $\lambda_2, \lambda_3$ satisfy:

    \lambda_1 + \lambda_2 + \lambda_3 = 3, \quad \lambda_1 \lambda_2 \lambda_3 = 2

  • Possible eigenvalues: $1, 1 \pm i$ (but $2 - i$ is not necessarily an eigenvalue).
  • Symmetric Matrix: Always diagonalizable.
  • Distinct Eigenvalues: Implies diagonalizable.

• Column Space (Q15):

  • Column space of $A$ = span of linearly independent columns.

  • For $A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 0 & 1 & 2 \end{pmatrix}$, the column space is:

    \text{span}\left\{ \begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix}, \begin{pmatrix} 2 \\ 3 \\ 1 \end{pmatrix} \right\}

    (Equivalent to option D after simplification.)

• Least Squares & Mean of Data (Q11):

  • The point $q$ minimizing $g(p) = \sum \|p - x_i\|^2$ is the mean of the data.

  • Implication:

    q = \frac{1}{10} \sum_{i=1}^{10} x_i \Rightarrow \sum_{i=1}^{10} x_i = 10q = \begin{pmatrix} 30 \\ 0 \\ 30 \end{pmatrix}

  • Distance from origin:

    \left\| \sum x_i \right\| = \sqrt{30^2 + 0^2 + 30^2} = 30\sqrt{2}

F. Dimensionality Reduction (PCA)

• Principal Component Analysis (PCA) (Q12):

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

  • Steps:

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

  • Key Points:

    • Reduces dimensionality while preserving variance.
    • Does not maximize reconstruction error (that’s the opposite goal).

Graph 2: Probability & Statistics

Graph 3: Linear Algebra & PCA

Graph 4: Calculus-Based Optimization

3. Key Equations Summary