ISRO Scientist/Engineer SC (Computer Science) key terms

A formula of propositional logic that evaluates to true under every possible truth assignment to its variables; its negation is unsatisfiable.

A binary relation on a set that is reflexive, symmetric, and transitive; it partitions the set into disjoint equivalence classes whose members are treated as interchangeable.

A binary relation that is reflexive, antisymmetric, and transitive; it orders some pairs of elements without requiring every pair to be comparable.

A partially ordered set in which every pair of elements has a least upper bound and a greatest lower bound; finite lattices underlie Boolean algebra and dataflow analysis.

A set with an associative binary operation, an identity element, and an inverse for every element; groups model symmetries and underlie error-correcting codes and cryptography.

A scalar lambda for which a nonzero vector v satisfies Av = lambda v for a square matrix A; eigenvalues reveal stability, diagonalizability, and characteristic behavior of linear transformations.

A rule relating conditional probabilities: P(A|B) = P(B|A)P(A)/P(B); it updates a prior belief about A after observing evidence B.

A function that assigns a real number to each outcome in a sample space, enabling probabilities of numerical events and the definition of expectation and variance.

A grid diagram that represents a Boolean function so adjacent cells differ in one variable, and grouping cells yields a simplified sum-of-products or product-of-sums expression.

A bistable digital storage element that holds one bit and changes state on a clock edge or control signal; registers and counters are built from flip-flops.

A cache organization in which each memory block can occupy one of several lines within a fixed set, balancing direct-mapped speed against fully associative flexibility.

A condition in an instruction pipeline that prevents the next instruction from starting or completing in its scheduled cycle, often due to data, control, or structural conflicts.

A method that bounds the average cost per operation over a worst-case sequence of operations, even when individual operations are occasionally expensive.

A situation where two distinct keys map to the same slot in a hash table; resolved by chaining, open addressing, or related techniques.

A binary search tree that maintains height logarithmic in the number of nodes through rotations or restructuring, guaranteeing efficient search, insertion, and deletion.

A pointer that still holds the address of memory that has been freed or deallocated; dereferencing it causes undefined behavior and possible security vulnerabilities.

A technique that solves problems with overlapping subproblems by storing subproblem results, typically combining optimal substructure with a table or memoized recursion.

An algorithm that builds a solution by repeatedly making the locally best choice, correct only when the problem exhibits a matroid-like or exchange property.

A subset of edges in a connected weighted undirected graph that connects all vertices with minimum total edge weight and contains no cycle.

A property of decision problems that are in NP and NP-hard, meaning every NP problem reduces to them in polynomial time and no polynomial algorithm is known.

A formula for solving divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n) with n raised to log base b of a.

A necessary property of regular languages stating that sufficiently long strings can be split and pumped while remaining in the language; used to prove non-regularity.

A formal grammar with productions whose left side is a single nonterminal; it generates context-free languages recognized by pushdown automata and parsed by compilers.

A top-down parsing method that predicts productions using one lookahead token; the grammar must have disjoint FIRST and FOLLOW-based selection sets.

An intermediate representation in which each instruction has at most one operator and up to three operands, making control flow and optimization explicit for compilers.

The counterintuitive situation in FIFO page replacement where increasing the number of page frames increases the number of page faults for some reference strings.

A synchronization variable with an integer value and atomic wait and signal operations, used to control access to shared resources and coordinate concurrent processes.

A condition in which a system spends most of its time servicing page faults and little time executing useful work, usually because the resident set is too small.

A relation schema in which every non-prime attribute is nontrivially dependent only on candidate keys, eliminating transitive dependencies on non-key attributes.

A concurrency-control protocol requiring each transaction to acquire all locks before releasing any, with a growing phase followed by a shrinking phase.

The transaction properties atomicity, consistency, isolation, and durability, which guarantee all-or-nothing execution, valid state transitions, concurrent independence, and permanent committed effects.

Classless Inter-Domain Routing, an addressing scheme using variable-length prefixes written as address and prefix length to aggregate routes and conserve IPv4 address space.

A set of mechanisms including slow start, congestion avoidance, fast retransmit, and fast recovery that adapt TCP sending rate to inferred network capacity.

The Address Resolution Protocol, which maps a known IPv4 address to a link-layer MAC address on a local network through broadcast request and unicast reply.

A software metric equal to E minus N plus 2P for a control-flow graph, measuring the number of linearly independent paths and guiding basis-path testing.

Two design metrics: cohesion measures how strongly elements inside a module belong together, while coupling measures how much modules depend on one another.

A name-resolution rule in which a variable reference is bound according to the textual nesting of declarations, not according to the caller's environment.

A function value paired with the lexical environment in which it was created, allowing it to access captured variables after the enclosing scope returns.

A browser security rule restricting scripts from one origin from reading or modifying resources of another origin, where origin combines scheme, host, and port.

An architectural style for networked applications using stateless requests, resource identifiers, standard HTTP methods, and representations that may be cached.