GATE CS key terms

A description of how an algorithm's running time or memory grows as input size increases, ignoring constant factors and lower-order terms. Usually expressed with Big-O, Big-Omega, or Big-Theta notation.

An upper-bound notation stating that a function grows no faster than a given rate for sufficiently large inputs. For example, O(n log n) means growth is bounded by n log n up to a constant factor.

A method of averaging the cost of operations over a sequence of worst-case executions, so an occasionally expensive operation is charged across many cheap ones. Common techniques are aggregate, accounting, and potential methods.

An equation expressing the cost of a recursive algorithm in terms of smaller inputs, such as T(n)=2T(n/2)+n. Solved by substitution, recursion trees, or the Master Theorem to obtain asymptotic bounds.

A formula giving asymptotic solutions to divide-and-conquer recurrences of the form T(n)=aT(n/b)+f(n). It compares f(n) with n raised to log base b of a to select the dominant term.

An array that grows automatically when full, typically by allocating a larger block and copying elements. Insertion at the end is amortized O(1) despite occasional O(n) resizing costs.

A data structure mapping keys to values using a hash function to compute bucket indices. Average lookup, insertion, and deletion are O(1), but collisions and poor hash functions can degrade performance to O(n).

A collision-resolution scheme in hash tables where all entries reside in the table itself. On collision, the probe sequence (linear, quadratic, or double hashing) searches for the next free slot.

The ratio of stored entries to table slots in a hash structure. As it approaches one, collisions increase sharply, so tables resize and rehash to keep operations near constant time.

A search tree that keeps height logarithmic by restructuring after insertions and deletions. Examples include AVL trees and red-black trees, both guaranteeing O(log n) search, insert, and delete.

A binary tree where every node's left subtree holds smaller keys and its right subtree larger keys. Search cost equals tree height, which can degenerate to O(n) if the tree is unbalanced.

A complete binary tree satisfying the heap property, where each parent is no smaller (max-heap) or no larger (min-heap) than its children. Supports O(log n) insertion and extract-min or extract-max.

An abstract data type that returns the element with highest priority first. Often implemented with a binary heap, giving O(log n) insert and extract operations and O(1) peek.

An algorithm design paradigm that splits a problem into independent subproblems, solves them recursively, and combines results. Examples include merge sort, quicksort, and binary search.

A technique solving problems with overlapping subproblems by storing computed results in a table. It requires optimal substructure and is applied to shortest paths, knapsack, and sequence alignment.

A top-down optimization that caches results of function calls keyed by their arguments, avoiding recomputation. It turns exponential recursive algorithms into polynomial ones when subproblems overlap.

A strategy making the locally best choice at each step, hoping for a global optimum. Correct only when the problem has the greedy-choice property and optimal substructure, as in minimum spanning trees.

A single-source shortest-path algorithm for graphs with nonnegative edge weights. It repeatedly settles the closest unsettled vertex using a priority queue, running in O((V+E) log V) with a binary heap.

A single-source shortest-path algorithm that relaxes every edge V-1 times, handling negative weights and detecting negative cycles. Its running time is O(VE).

A subset of edges connecting all vertices of a weighted undirected graph with minimum total weight and no cycles. Found by Kruskal's or Prim's algorithms.

A linear ordering of a directed acyclic graph's vertices such that every edge points forward. Used for dependency scheduling and computed by depth-first search or Kahn's algorithm.

A graph traversal that explores as far as possible along each branch before backtracking, using recursion or a stack. It runs in O(V+E) and supports cycle detection and topological sorting.

A graph traversal exploring all neighbors at the current distance before moving farther, using a queue. It runs in O(V+E) and finds shortest paths in unweighted graphs.

A directed graph containing no directed cycles. It models precedence constraints and always admits at least one topological ordering of its vertices.

A property 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=NP.

A transformation of one problem into another computable in polynomial time, used to show relative hardness. If A reduces to B and B is easy, then A is easy; conversely hardness transfers backward.

The open question of whether every problem whose solution can be verified quickly can also be solved quickly. Most researchers believe P is a strict subset of NP.

A formal grammar with rules rewriting a single nonterminal into a string of terminals and nonterminals. It generates context-free languages recognized by pushdown automata and parsed by algorithms such as CYK.

A language describable by a regular expression, finite automaton, or right-linear grammar. Regular languages are closed under union, intersection, and complement and are a strict subset of context-free languages.

A necessary condition used to prove a language is not regular or not context-free. It states that sufficiently long strings can be split and a middle part repeated while staying in the language.

The process of analyzing a token stream against a grammar to build a syntax tree. Techniques include LL top-down parsing and LR bottom-up parsing, used in compilers.

The compiler phase converting a character stream into tokens using regular expressions and finite automata. Its output feeds the parser and it typically discards whitespace and comments.

An intermediate representation where each instruction has at most one operator and three operands, such as t1 = a + b. It simplifies optimization and target code generation in compilers.

The compiler phase assigning program variables to a limited set of CPU registers, often modeled as graph coloring. Spilling to memory occurs when registers are insufficient.

The property ensuring multiple processor caches in a shared-memory system agree on memory contents. Protocols such as MESI maintain consistency through invalidation or update messages.

A processor technique overlapping execution of multiple instructions by splitting work into stages. Hazards (data, control, structural) limit speedup and are mitigated by forwarding and stalls.

The degree to which independent instructions in a program can execute simultaneously. Exploited by superscalar processors through out-of-order execution and speculative techniques.

An abstraction giving each process a private address space mapped to physical memory via page tables. It enables protection and demand paging, with translation accelerated by a TLB.

An exception raised when a program accesses a virtual page not currently in physical memory. The operating system loads the page from disk, possibly evicting another page.

A severe performance collapse where the system spends most time swapping pages rather than executing processes. It occurs when the working set exceeds available physical memory.

A state where a set of processes each wait for resources held by others, so none can proceed. It requires mutual exclusion, hold-and-wait, no preemption, and circular wait simultaneously.

A deadlock-avoidance algorithm that grants resource requests only if the system remains in a safe state, where all processes can eventually complete. It requires advance knowledge of maximum demands.

A synchronization primitive with an integer counter and atomic wait and signal operations. Counting semaphores manage multiple resource units, while binary semaphores act as mutual-exclusion locks.

A code region accessing shared data that must not be executed concurrently by more than one process. Solutions must ensure mutual exclusion, progress, and bounded waiting.

The database design process organizing relations to reduce redundancy and update anomalies. It progresses through normal forms, from first normal form up to BCNF and beyond.

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

A relation schema where every nontrivial functional dependency has a superkey on its left side. It is stricter than third normal form and eliminates certain redundancy anomalies.

Four guarantees for database transactions: atomicity (all or nothing), consistency (valid state transitions), isolation (concurrent transactions do not interfere), and durability (committed changes persist).

The correctness criterion for concurrent transaction schedules, requiring an outcome equivalent to some serial execution. Conflict serializability is checked with a precedence graph.

A concurrency control protocol where a transaction acquires all locks in a growing phase, then releases them in a shrinking phase. It guarantees conflict serializability but can cause deadlock.

Mechanisms adjusting the sender's transmission rate to avoid network overload. Slow start, congestion avoidance, fast retransmit, and fast recovery respond to packet loss and acknowledgments.

A reliable data-transfer technique allowing multiple unacknowledged frames in flight up to a window size. It provides flow control and efficient use of links, using go-back-N or selective repeat.

Dividing a large IP network into smaller logical subnets using a subnet mask. It improves routing efficiency and address utilization, with hosts computed from host bits.

A compact representation of an IP address and its network prefix length, such as 192.168.1.0/24. It enables classless routing and route aggregation.

Encryption using a key pair where the public key encrypts and the private key decrypts, or vice versa for signatures. It solves key distribution but is slower than symmetric ciphers.

A cryptographic value proving a message's origin and integrity. The sender signs a hash with the private key; anyone can verify with the public key, providing authentication and non-repudiation.

A deterministic function mapping arbitrary-length input to a fixed-length digest. Cryptographic hashes must be preimage-resistant, collision-resistant, and fast, supporting integrity checks and signatures.