Formula sheet · GATE DA Atlas

Every formula, fact and complexity bound from the guide on one page, organised by syllabus section, for last-week revision. Each section links back to the full pages.

Probability and statistics

Counting — $n!$ · $^nP_r = \tfrac{n!}{(n-r)!}$ · $\binom nr = \tfrac{n!}{r!(n-r)!}$ · repetition allowed: $\binom{n+r-1}{r}$ · derangements $D_n = n!\sum_{k=0}^n\tfrac{(-1)^k}{k!}$ · inclusion–exclusion $|A\cup B| = |A| + |B| - |A\cap B|$ .

Rules — $P(A\cup B) = P(A) + P(B) - P(A\cap B)$ · $P(A\mid B) = \tfrac{P(A\cap B)}{P(B)}$ · independent: $P(A\cap B) = P(A)P(B)$ · total probability $P(B) = \sum_i P(B\mid A_i)P(A_i)$ · Bayes $P(A_i\mid B) = \tfrac{P(B\mid A_i)P(A_i)}{\sum_j P(B\mid A_j)P(A_j)}$ .

Expectation and variance — $E[aX + b] = aE[X] + b$ · $\text{Var}(X) = E[X^2] - (E[X])^2$ · $\text{Var}(aX + b) = a^2\text{Var}(X)$ · $\text{Var}(X + Y) = \text{Var}X + \text{Var}Y + 2\text{Cov}(X, Y)$ · $\text{Cov}(X, Y) = E[XY] - E[X]E[Y]$ · $\rho = \tfrac{\text{Cov}}{\sigma_X\sigma_Y} \in [-1, 1]$ .

Distribution	PMF / PDF	Mean	Variance
Bernoulli( $p$ )	$p^x(1-p)^{1-x}$	$p$	$p(1-p)$
Binomial( $n, p$ )	$\binom nx p^x(1-p)^{n-x}$	$np$	$np(1-p)$
Geometric( $p$ ), trials to 1st success	$(1-p)^{x-1}p$	$1/p$	$(1-p)/p^2$
Poisson( $\lambda$ )	$e^{-\lambda}\lambda^x/x!$	$\lambda$	$\lambda$
Uniform( $a, b$ )	$\tfrac1{b-a}$	$\tfrac{a+b}2$	$\tfrac{(b-a)^2}{12}$
Exponential( $\lambda$ )	$\lambda e^{-\lambda x}$	$1/\lambda$	$1/\lambda^2$
Normal( $\mu, \sigma^2$ )	$\tfrac1{\sigma\sqrt{2\pi}}e^{-(x-\mu)^2/2\sigma^2}$	$\mu$	$\sigma^2$

Memoryless: geometric and exponential. Normal: 68–95–99.7 rule; $z = (x - \mu)/\sigma$ ; $z_{0.025} = 1.96$ , $z_{0.05} = 1.645$ .

Inference — $\bar X \sim N(\mu, \sigma^2/n)$ (CLT) · standard error $\sigma/\sqrt n$ · CI $\bar x \pm z_{\alpha/2}\sigma/\sqrt n$ (use $t_{n-1}$ and $s$ when $\sigma$ unknown) · sample variance $s^2 = \tfrac1{n-1}\sum(x_i - \bar x)^2$ · $z = \tfrac{\bar x - \mu_0}{\sigma/\sqrt n}$ · $t = \tfrac{\bar x - \mu_0}{s/\sqrt n}$ · $\chi^2 = \sum\tfrac{(O - E)^2}{E}$ · Type I error $= \alpha$ , Type II $= \beta$ , power $= 1 - \beta$ .

Full pages: Probability & Statistics.

Linear algebra

Subspace: contains $\mathbf 0$ , closed under $+$ and scalar multiplication. Basis = linearly independent spanning set.
Rank–nullity: $\text{rank}(A) + \text{nullity}(A) = n$ (number of columns). Row rank = column rank.
$A\mathbf x = \mathbf b$ is consistent iff $\text{rank}(A) = \text{rank}([A\mid\mathbf b])$ ; unique iff also $= n$ .
$\det(AB) = \det A\det B$ · $\det(A^T) = \det A$ · $\det(kA) = k^n\det A$ · $\det(A^{-1}) = 1/\det A$ · triangular: product of the diagonal.
Eigenvalues: $\det(A - \lambda I) = 0$ · $\sum\lambda_i = \text{tr}(A)$ · $\prod\lambda_i = \det A$ · eigenvalues of $A^k$ : $\lambda^k$ ; of $A^{-1}$ : $1/\lambda$ ; of $A + cI$ : $\lambda + c$ · triangular: diagonal entries · symmetric: real eigenvalues, orthogonal eigenvectors.
Diagonalisable iff $n$ independent eigenvectors (sufficient: $n$ distinct eigenvalues). $A = PDP^{-1}$ .
Special matrices: orthogonal $Q^TQ = I$ ( $|\lambda| = 1$ , $\det = \pm1$ ) · idempotent $P^2 = P$ ( $\lambda\in\{0, 1\}$ , rank = trace) · nilpotent ( $\lambda = 0$ ) · projection onto the column space of $A$ : $P = A(A^TA)^{-1}A^T$ ; onto $\mathbf a$ : $\tfrac{\mathbf a\mathbf a^T}{\mathbf a^T\mathbf a}$ .
Quadratic form $\mathbf x^TA\mathbf x$ : positive definite iff all eigenvalues $> 0$ iff all leading principal minors $> 0$ .
LU: $A = LU$ (Gaussian elimination). SVD: $A = U\Sigma V^T$ , singular values $\sigma_i = \sqrt{\lambda_i(A^TA)}$ , rank = number of nonzero $\sigma_i$ , best rank- $k$ approximation keeps the top $k$ .

Full pages: Linear Algebra.

Calculus and optimisation

Standard limits: $\lim_{x\to0}\tfrac{\sin x}{x} = 1$ , $\lim\tfrac{e^x - 1}{x} = 1$ , $\lim\tfrac{\ln(1+x)}{x} = 1$ , $\lim_{x\to\infty}(1 + \tfrac1x)^x = e$ . L'Hôpital for $\tfrac00$ and $\tfrac\infty\infty$ .
Differentiable ⇒ continuous (not conversely: $|x|$ at 0).
Mean value theorem: $f'(c) = \tfrac{f(b) - f(a)}{b - a}$ for some $c\in(a, b)$ .
Taylor: $f(x) = \sum_k\tfrac{f^{(k)}(a)}{k!}(x - a)^k$ . $e^x = \sum\tfrac{x^k}{k!}$ · $\sin x = x - \tfrac{x^3}{3!} + \dots$ · $\cos x = 1 - \tfrac{x^2}{2!} + \dots$ · $\ln(1 + x) = x - \tfrac{x^2}2 + \tfrac{x^3}3 - \dots$ · $\tfrac1{1-x} = \sum x^k$ .
Extrema: $f'(c) = 0$ ; $f'' > 0$ min, $f'' < 0$ max; if $f'' = 0$ use the first nonzero higher derivative (even order → extremum). On $[a, b]$ also check the endpoints.
Gradient descent $x_{k+1} = x_k - \eta f'(x_k)$ · Newton $x_{k+1} = x_k - f'(x_k)/f''(x_k)$ . Convex: $f'' \ge 0$ , every local minimum is global.
Integration by parts $\int u\,dv = uv - \int v\,du$ · $\int_0^\infty x^ne^{-x}dx = n!$ · $\int_{-\infty}^\infty e^{-x^2}dx = \sqrt\pi$ .

Full pages: Calculus.

Programming, data structures and algorithms

Algorithm / structure	Time	Notes
Binary search	$O(\log n)$	sorted array
Insertion sort	$O(n^2)$ , best $O(n)$	stable, in place; adaptive
Selection sort	$O(n^2)$ always	not stable; at most $n - 1$ swaps
Bubble sort	$O(n^2)$ , best $O(n)$ with flag	stable
Merge sort	$O(n\log n)$	stable, $O(n)$ extra space
Quicksort	avg $O(n\log n)$ , worst $O(n^2)$	in place, not stable
Heap: build / insert / extract	$O(n)$ / $O(\log n)$ / $O(\log n)$
Hash table	avg $O(1)$ ; chaining expected length $\alpha = n/m$
BST search	$O(h)$ : $O(\log n)$ balanced, $O(n)$ worst	inorder = sorted
BFS / DFS	$O(V + E)$	BFS gives shortest paths in unweighted graphs
Dijkstra (binary heap)	$O((V + E)\log V)$	no negative edges
Topological sort	$O(V + E)$	DAG only
Kruskal / Prim	$O(E\log E)$ / $O(E\log V)$	minimum spanning tree

Comparison sorting lower bound $\Omega(n\log n)$ . Master theorem for $T(n) = aT(n/b) + \Theta(n^d)$ : $d > \log_b a$ → $\Theta(n^d)$ ; $=$ → $\Theta(n^d\log n)$ ; $<$ → $\Theta(n^{\log_b a})$ .
Binary tree: max nodes at height $h$ : $2^{h+1} - 1$ ; $n_0 = n_2 + 1$ ; complete tree height $\lfloor\log_2 n\rfloor$ . Heap children of $i$ (0-based): $2i + 1$ , $2i + 2$ .
Graphs: $\sum\deg = 2E$ ; a tree has $V - 1$ edges; simple graph has at most $\binom V2$ edges.
Python: mutable default arguments persist; // floors toward $-\infty$ ; slicing copies; is vs ==.

Full pages: Programming & DSA.

DBMS and warehousing

Keys: superkey ⊇ candidate key (minimal) ∋ primary key. Closure $X^+$ decides whether $X$ is a key.
Armstrong's axioms: reflexivity, augmentation, transitivity (+ union, decomposition, pseudo-transitivity).
Normal forms: 1NF atomic · 2NF no partial dependency on a key · 3NF for every $X\to A$ , $X$ superkey or $A$ prime · BCNF every $X\to A$ has $X$ superkey. Lossless join (binary) iff $R_1\cap R_2\to R_1$ or $\to R_2$ .
Relational algebra: $\sigma, \pi, \times, \bowtie, \cup, -, \div, \rho$ ; $|R\times S| = |R||S|$ ; natural join on no common attribute = cross product.
SQL: WHERE filters rows before grouping, HAVING filters groups; COUNT(*) counts NULLs, COUNT(col) does not; comparisons with NULL are unknown.
B+ tree of order $p$ : nodes hold $\lceil p/2\rceil$ to $p$ pointers; all data at leaves. Index levels $\approx\lceil\log_{\text{fanout}}(\text{records})\rceil$ .
Normalisation of data: min–max $\tfrac{x - \min}{\max - \min}$ , z-score $\tfrac{x - \mu}{\sigma}$ . Warehousing: star schema (fact + denormalised dimensions), snowflake (normalised dimensions); OLAP roll-up, drill-down, slice, dice, pivot; a cube with $n$ dimensions has $2^n$ cuboids (without hierarchies).

Full pages: DBMS.

Machine learning

Linear regression: $\hat{\boldsymbol\beta} = (X^TX)^{-1}X^T\mathbf y$ ; simple: $\hat\beta_1 = \tfrac{\text{Cov}(x, y)}{\text{Var}(x)}$ , $\hat\beta_0 = \bar y - \hat\beta_1\bar x$ ; $R^2 = 1 - \tfrac{SS_{res}}{SS_{tot}}$ .
Ridge: $(X^TX + \lambda I)^{-1}X^T\mathbf y$ (shrinks; never exactly zero) · Lasso ( $\ell_1$ ) gives sparsity.
Logistic: $\sigma(z) = \tfrac1{1 + e^{-z}}$ , $\sigma' = \sigma(1 - \sigma)$ ; log-odds linear; cross-entropy loss; gradient $X^T(\sigma(X\mathbf w) - \mathbf y)$ .
k-NN: no training; small $k$ → high variance, large $k$ → high bias. Naive Bayes: $P(c\mid\mathbf x)\propto P(c)\prod_j P(x_j\mid c)$ ; Laplace smoothing $\tfrac{n_{jc} + 1}{n_c + V}$ .
LDA: shared covariance → linear boundary; Fisher direction $\mathbf w\propto S_W^{-1}(\boldsymbol\mu_1 - \boldsymbol\mu_2)$ .
SVM: maximise margin $\tfrac2{\|\mathbf w\|}$ s.t. $y_i(\mathbf w^T\mathbf x_i + b)\ge1$ ; hinge loss $\max(0, 1 - yf(x))$ ; kernels $K(\mathbf x, \mathbf z) = \phi(\mathbf x)^T\phi(\mathbf z)$ .
Trees: entropy $H = -\sum p_i\log_2 p_i$ , Gini $1 - \sum p_i^2$ , information gain $= H(\text{parent}) - \sum\tfrac{n_k}{n}H(k)$ .
Bias–variance: $E[(y - \hat f)^2] = \text{bias}^2 + \text{variance} + \sigma^2$ . $k$ -fold CV trains $k$ models; LOOCV trains $n$ .
Neural networks: MLP with one hidden layer is a universal approximator; parameters of a dense layer $= n_{in}n_{out} + n_{out}$ ; ReLU $\max(0, z)$ ; backprop = chain rule.
k-means: minimises $\sum\|\mathbf x - \boldsymbol\mu_{c(\mathbf x)}\|^2$ , converges to a local optimum. Linkage: single (min), complete (max), average.
PCA: eigenvectors of the covariance matrix; variance explained by component $k$ = $\lambda_k/\sum\lambda_i$ .
Metrics: precision $\tfrac{TP}{TP + FP}$ , recall $\tfrac{TP}{TP + FN}$ , $F_1 = \tfrac{2PR}{P + R}$ , accuracy $\tfrac{TP + TN}{\text{all}}$ .

Full pages: Machine Learning.

Artificial intelligence

Search	Complete	Optimal	Time	Space
BFS	yes ( $b$ finite)	yes (unit costs)	$O(b^d)$	$O(b^d)$
Uniform-cost	yes ( $\epsilon > 0$ )	yes	$O(b^{1 + \lfloor C^*/\epsilon\rfloor})$	same
DFS	no (infinite / cycles)	no	$O(b^m)$	$O(bm)$
Depth-limited	no	no	$O(b^\ell)$	$O(b\ell)$
Iterative deepening	yes	yes (unit costs)	$O(b^d)$	$O(bd)$
Greedy best-first	no (tree search)	no	$O(b^m)$	$O(b^m)$
A*	yes	yes if $h$ admissible (tree) / consistent (graph)	exponential	exponential

$f = g + h$ . Admissible: $h(n)\le h^*(n)$ . Consistent: $h(n)\le c(n, n') + h(n')$ (consistent ⇒ admissible). $\max(h_1, h_2)$ of admissible heuristics is admissible and dominates.
Minimax $O(b^m)$ ; alpha–beta with perfect ordering $O(b^{m/2})$ ; prune when $\alpha\ge\beta$ .
Logic: $p\to q\equiv\neg p\vee q\equiv\neg q\to\neg p$ · KB $\models\alpha$ iff KB $\wedge\neg\alpha$ unsatisfiable · resolution · Horn clauses: forward/backward chaining · $\neg\forall x\,P\equiv\exists x\,\neg P$ · "All $P$ are $Q$ ": $\forall x(P\to Q)$ ; "Some $P$ are $Q$ ": $\exists x(P\wedge Q)$ .
Bayesian networks: $P(x_1..x_n) = \prod P(x_i\mid\text{parents})$ ; Boolean node with $k$ parents: $2^k$ numbers; chain/fork blocked by observing the middle; collider blocked unless it or a descendant is observed; Markov blanket = parents + children + co-parents.
Inference: $P(X\mid\mathbf e) = \alpha\sum_{\mathbf y}P(X, \mathbf e, \mathbf y)$ · VE: multiply factors with $H$ , sum out $H$ · polytrees linear, general NP-hard · rejection sampling keeps fraction $P(\mathbf e)$ · likelihood weighting $w = \prod P(e_j\mid\text{parents})$ · Gibbs: sample from $P(x_i\mid\text{Markov blanket})$ .

Full pages: AI.

General aptitude

Successive % changes $a + b + \tfrac{ab}{100}$ · km/h × 5/18 = m/s · together $\tfrac{ab}{a + b}$ · average speed $\tfrac{2uv}{u + v}$ · CI − SI (2 yrs) $= P(R/100)^2$ · clock angle $|30H - 5.5M|$ · mirror clock $11{:}60 - t$ · painted cube $8, 12(n-2), 6(n-2)^2, (n-2)^3$ · squares in an $n\times n$ grid $\sum k^2$ .

Full pages: General Aptitude.