GATE BM key terms

An equation expressing each term of a sequence as a fixed linear combination of earlier terms, often solved with characteristic roots to obtain closed forms and used in algorithm and combinatorics problems.

The polynomial equation obtained by assuming a solution of the form r^n for a linear recurrence or of the form e^(λx) for a linear differential equation; its roots determine the general solution.

A formal power series whose coefficients encode the terms of a sequence, allowing counting and recurrence problems to be solved by algebraic manipulation of the series.

A scalar λ for which a nonzero vector v satisfies Av = λv for a square matrix A; eigenvalues govern stability, diagonalisability, and many engineering vibration and control problems.

The dimension of the vector space spanned by the columns (or rows) of a matrix, equal to the number of linearly independent columns; it decides consistency of linear systems.

A property of a set of vectors where no vector can be written as a linear combination of the others, equivalently the only solution of the combination equal to zero has all coefficients zero.

A property of a symmetric matrix where the quadratic form x^T A x is strictly positive for every nonzero vector x, equivalent to all eigenvalues being positive and to a Cholesky factorisation existing.

The pair of partial differential equations relating the real and imaginary parts of a complex function; satisfying them together with continuity of partial derivatives makes the function analytic.

Evaluation of an integral of a complex function along a path in the complex plane, often using Cauchy's theorem or the residue theorem to convert it into a sum of residues.

An integral transform that maps a function of time to a function of a complex variable, converting linear differential equations with initial conditions into algebraic equations.

A representation of a periodic function as a sum of sines and cosines at integer multiples of the fundamental frequency, with coefficients computed by integration over one period.

An equation involving partial derivatives of an unknown function of several variables, classified as elliptic, parabolic, or hyperbolic, modelling heat, wave, and potential phenomena.

A technique for solving first-order partial differential equations by transforming them into ordinary differential equations along special curves called characteristics in the independent-variable plane.

A rule assigning probabilities to values or intervals of a random variable, given by a probability mass function for discrete variables or a density for continuous variables.

A method of estimating unknown parameters by choosing values that maximise the likelihood of the observed sample, often found by setting derivatives of the log-likelihood to zero.

The result that the sum or average of many independent, identically distributed random variables with finite variance approaches a normal distribution as the sample size grows.

A procedure that compares sample data against a null hypothesis using a test statistic, deciding rejection based on a chosen significance level and resulting p-value.

A range of values, computed from sample data, that is expected to contain an unknown population parameter with a stated probability under repeated sampling.

An iterative root-finding scheme using the tangent line at the current estimate, with update x_{n+1} = x_n - f(x_n)/f'(x_n); it converges quadratically near a simple root.

Approximate evaluation of a definite integral from sampled function values, using rules such as trapezoidal or Simpson's, with error depending on step size and derivative bounds.

A description of how the running time of an algorithm grows with input size, usually expressed in asymptotic notation such as O(n log n) or Θ(n^2).

An algorithm design technique that solves a problem by combining solutions to overlapping subproblems, storing intermediate results to avoid recomputation, and requiring optimal substructure.

A strategy that builds a solution step by step, always making the locally best choice, correct only when the problem exhibits the greedy-choice property and optimal substructure.

A binary tree in which every node's left subtree holds smaller keys and right subtree holds larger keys, supporting search, insertion, and deletion in time proportional to height.

A formal grammar whose production rules each rewrite a single nonterminal symbol, generating context-free languages that can be recognised by pushdown automata and parsed by stacks.

A language recognised by a finite automaton or described by a regular expression; it is closed under union, concatenation, and star but not under general intersection with context-free languages.

A formal query language over relations using operators such as selection, projection, join, and set difference, forming the theoretical basis for SQL query evaluation.

The process of organising relational schemas to reduce redundancy and update anomalies by decomposing tables according to functional dependencies into progressively stricter normal forms.

A memory-management scheme giving each process an independent logical address space mapped to physical frames through page tables, enabling protection and demand paging.

A state where a set of processes each wait indefinitely for a resource held by another in the set, requiring mutual exclusion, hold-and-wait, no preemption, and circular wait.

A sampling rule stating that a bandlimited signal must be sampled at more than twice its highest frequency to allow exact reconstruction without aliasing.

A plot in the complex plane of the closed-loop poles of a feedback system as a gain parameter varies, used to assess stability and transient response.

A network theorem stating that any linear two-terminal circuit can be replaced by an equivalent voltage source in series with a resistance, determined from open-circuit voltage and short-circuit current.

A linear-circuit principle allowing the response to several independent sources to be found by summing the responses to each source acting alone with others deactivated.

A graph plotting applied stress against resulting strain for a material, revealing elastic modulus, yield point, ultimate strength, and ductility under a specified loading condition.

The ratio of a material's or structure's failure strength to the expected working stress, providing margin against uncertainty in loads, material properties, and analysis.

A dimensionless ratio of inertial to viscous forces in fluid flow, used to predict whether flow is laminar or turbulent and to scale model experiments.

A relation for steady, incompressible, inviscid flow along a streamline stating that pressure, kinetic, and potential energy per unit volume sum to a constant.

The maximum possible efficiency of a heat engine operating between two thermal reservoirs, equal to one minus the ratio of absolute sink temperature to source temperature.

The principle that entropy of an isolated system cannot decrease, limiting the direction of spontaneous processes and forbidding a device that converts heat entirely into work in a cycle.