GATE CY key terms

An ordering of strings, tuples, or permutations where elements are compared position by position, the first differing position deciding the result, exactly as in a dictionary. GATE uses it to define canonical output for permutations and sorting problems.

An arrangement of a set of distinct items in a specific order. The number of permutations of n distinct items is n factorial, a fact used in counting problems and in generating all orderings.

An equation expressing a sequence value in terms of earlier values, such as T(n) = 2T(n/2) + n. Solving it yields closed-form or asymptotic growth, typically via the Master Theorem or substitution.

A recipe for solving divide-and-conquer recurrences T(n) = aT(n/b) + f(n) by comparing f(n) with n raised to log base b of a, giving the asymptotic bound directly in three standard cases.

A description of how a function grows as its input size becomes large, ignoring constants and lower-order terms. Written with Big-O, Big-Omega, or Big-Theta notation to classify algorithm cost.

Averaging the cost of a sequence of operations over the whole sequence rather than per worst-case operation, giving a tighter bound. Used for dynamic arrays and union-find, where occasional expensive operations are rare.

A disjoint-set data structure supporting merge of two sets and query of which set an element belongs to. With union by rank and path compression, operations run in near-constant amortized time.

A subset of edges of a connected weighted graph that connects all vertices with minimum total weight and no cycle. Found by Kruskal's or Prim's algorithm; Kruskal's typically uses union-find.

A strategy that builds a solution by repeatedly making the locally best choice, never revisiting it. Correct only when the problem has the greedy-choice property and optimal substructure, as in interval scheduling.

A technique that solves overlapping subproblems once, stores results in a table, and combines them to answer the whole problem. Requires optimal substructure; used for knapsack, longest common subsequence, and matrix chain multiplication.

A property of regular and context-free languages used to prove a language is not in the class. It states that sufficiently long strings can be split so a middle part repeats while staying in the language.

A language accepted by a finite automaton or described by a regular expression, closed under union, intersection, complement, and concatenation. Its membership can be decided by a DFA in linear time.

A machine with finitely many states, one start state, accepting states, and exactly one transition per state and symbol. It recognizes precisely the regular languages, and its state count can be minimized.

A set of rewriting rules with a start symbol generating strings from nonterminals, allowing recursion such as balanced parentheses. Recognized by pushdown automata; used to define programming language syntax.

The problem of deciding, for an arbitrary program and input, whether the program eventually stops. Turing proved it undecidable, making it the standard example of a non-recursive language.

A transformation of one decision problem into another so that a solution to the second solves the first. Used to prove undecidability and NP-completeness by transferring hardness between problems.

A class of decision problems that are in NP and to which every NP problem reduces in polynomial time. Finding a polynomial algorithm for any one of them would imply P equals NP.

A property of a problem when a Turing machine exists that always halts and correctly answers yes or no for every input. Undecidable problems, such as the halting problem, lack any such machine.

The process of deriving a parse tree from a token stream according to a grammar. Top-down methods include recursive descent and LL(1); bottom-up methods include LR and operator precedence.

Auxiliary sets for predictive parsing. First of a symbol lists terminals that can begin strings derived from it; Follow lists terminals that can appear immediately after a nonterminal in some sentential form.

An intermediate representation where each instruction has at most one operator and three operands, such as t1 = a + b. Simple to generate and optimize, and common in compiler questions.

A maximal straight-line sequence of three-address statements with one entry and one exit, containing no jumps in or out except at the ends. Control-flow graphs are built from basic blocks.

A compiler optimization that detects repeated evaluation of the same expression and replaces later occurrences with the previously computed value, often using available-expression analysis on basic blocks.

A state where a set of processes each wait for a resource held by another in the set, so none can proceed. Prevented by ordering resources, avoided by Banker's algorithm, or detected and recovered from.

A synchronization variable with an integer value and atomic wait and signal operations. A binary semaphore acts as a mutex; a counting semaphore limits concurrent access to a pool of resources.

The act of saving the state of a running process and restoring another's so the CPU can be reassigned. It costs time and involves kernel mode, with no useful user work done during the switch.

An abstraction giving each process a private logical address space mapped to physical frames by page tables. Enables demand paging, protection, and programs larger than physical memory.

An interrupt raised when a program accesses a page not currently in physical memory, forcing the operating system to load it from disk and possibly evict another page.

The counterintuitive case where increasing the number of page frames increases the number of page faults under FIFO replacement. It does not occur with stack algorithms such as LRU.

Organizing relations to reduce redundancy and update anomalies by decomposing them according to functional dependencies, aiming for third normal form or Boyce-Codd normal form while preserving dependencies.

A constraint stating that whenever two tuples agree on attribute set X they must agree on set Y, written X yields Y. It drives key identification and normalization decisions.

A minimal set of attributes whose values uniquely identify each tuple in a relation. One candidate key is chosen as the primary key; the others remain alternate keys.

A concurrency-control protocol where a transaction acquires all locks in a growing phase before releasing any in a shrinking phase. Guarantees conflict serializability but can cause deadlock.

A flow-control scheme where the sender may transmit up to a window of unacknowledged frames. Window size and round-trip time bound throughput, especially with selective repeat or go-back-N.

A reliable transfer scheme sending one frame and waiting for its acknowledgement before sending the next. Simple but inefficient over links with long propagation delay relative to transmission time.

Dividing a network into smaller address blocks by borrowing bits from the host portion of an IP address. The subnet mask determines which bits identify the network.

Classless Inter-Domain Routing, which writes network prefixes as address followed by a slash and prefix length. It allows arbitrary-length prefixes and efficient route aggregation.

A small associative cache inside the memory management unit holding recent virtual-to-physical page translations. A hit avoids walking the page table, cutting address-translation latency.

The requirement that multiple caches in a multiprocessor system present a consistent view of memory. Protocols such as MESI track sharing and invalidate stale copies on writes.

A situation preventing the next instruction from executing in its scheduled clock cycle, caused by data dependence, control flow, or structural resource conflicts. Mitigated by forwarding and stalling.

A method for multiplying two signed binary numbers in two's complement without separate sign handling, recoding the multiplier into digits of plus one, zero, and minus one.

A signed binary representation where the most significant bit has negative weight, so negation is bitwise inversion plus one. It gives a single representation of zero and simple addition.

A grid arranging truth-table minterms so adjacent cells differ in one variable, allowing visual grouping into prime implicants and a minimal sum-of-products expression.

Timing constraints for a flip-flop: data must be stable for a minimum interval before the clock edge and remain stable for a minimum interval after it, otherwise metastability may occur.

Average-case constant time for insert, search, and delete with a good hash function and low load factor, degrading to linear time when many keys collide into one bucket.

A binary tree where each node's left subtree holds smaller keys and right subtree larger keys. Search, insert, and delete cost height, which is logarithmic only when balanced.

Operations on a pointer that add or subtract integers scaled by the size of the pointed-to type, and subtract two pointers to get element distance. Central to C array and string questions.