GATE CS flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Master theorem case 2

For T(n) = aT(n/b) + f(n), if f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) · log n). Example: T(n) = 2T(n/2) + n gives Θ(n log n).

Amortized analysis

Averages cost per operation over a worst-case sequence without probability assumptions. Methods are aggregate, accounting (potential credits), and potential. Dynamic array insertion is O(1) amortized despite O(n) occasional resizes.

Dijkstra precondition

Dijkstra's algorithm requires all edge weights to be non-negative. With negative edges it can finalize a vertex before a shorter path is discovered. Use Bellman-Ford instead, which runs in O(VE).

Union-Find complexity

With union by rank and path compression, m operations on n elements take O(m α(n)) time, where α is the inverse Ackermann function, effectively constant. Used in Kruskal's minimum spanning tree algorithm.

NP-complete proof recipe

Show the problem is in NP by giving a polynomial-time verifier, then pick a known NP-complete problem and reduce it to your problem in polynomial time. Both steps are required.

Halting problem decidability

The halting problem is undecidable: no Turing machine decides whether an arbitrary machine halts on a given input. It is recursively enumerable because a universal machine can simulate and accept if it halts.

Pumping lemma regular

For a regular language L there exists p such that every string w in L with |w| ≥ p can be written w = xyz where |xy| ≤ p, |y| ≥ 1, and xy^k z is in L for all k ≥ 0.

NFA to DFA bound

Subset construction converts an NFA with n states into a DFA with at most 2^n states, one per subset of NFA states. The exponential blowup is tight for some languages.

Context-free closure properties

Context-free languages are closed under union, concatenation, Kleene star, and homomorphism, but not under intersection or complement. Deterministic CFLs are closed under complement but not union.

LR vs LL parsing

LL parsers read input left to right and build a leftmost derivation; LR parsers build a rightmost derivation in reverse. LR handles strictly more grammars and detects syntax errors earlier.

BCNF condition

A relation is in Boyce-Codd normal form if for every nontrivial functional dependency X → Y, X is a superkey. BCNF is stricter than 3NF and may sacrifice dependency preservation.

Conflict serializability test

Build a precedence graph with a node per transaction and an edge Ti → Tj for each conflicting pair of operations where Ti accesses first. The schedule is conflict serializable exactly when the graph is acyclic.

Strict two-phase locking

A transaction acquires all locks before releasing any and holds exclusive locks until commit. This guarantees conflict serializability and cascadeless recovery, but deadlock remains possible.

ACID properties

Atomicity means all-or-nothing execution; consistency preserves database invariants; isolation makes concurrent transactions appear serial; durability means committed changes survive crashes, typically via write-ahead logging.

B+ tree properties

A B+ tree stores all keys in leaves linked for range scans, with internal nodes holding only separator keys. All leaves are at the same depth, giving O(log n) search, insert, and delete.

Cache AMAT formula

Average memory access time equals hit time plus miss rate times miss penalty. For two-level caches, AMAT = L1 hit time + L1 miss rate × (L2 hit time + L2 miss rate × memory penalty).

Pipeline speedup limit

An ideal k-stage pipeline gives speedup approaching k, but hazards, stalls, and register overhead reduce it. Speedup is bounded by 1 divided by the pipeline register delay fraction.

Amdahl's law

Speedup = 1 / ((1 - f) + f/s), where f is the fraction of execution enhanced and s the improvement factor. Even infinite s yields speedup bounded by 1/(1 - f).

Two's complement range

An n-bit two's complement integer ranges from -2^(n-1) to 2^(n-1) - 1. Negation flips all bits and adds one; overflow occurs when adding two same-sign operands yields the opposite sign.

Karnaugh map grouping

Group 1s in powers of two (1, 2, 4, 8) with wraparound at edges to form minimal sum-of-products terms. Don't-care entries may be grouped to enlarge groups and simplify the expression.

Setup and hold time

Setup time requires data stable before the clock edge; hold time requires it stable after. Violations cause metastability. Maximum clock frequency is limited by the longest combinational path plus setup time.

TCP congestion control phases

Slow start doubles the congestion window each RTT until the threshold; congestion avoidance increases it by one MSS per RTT; on loss, the threshold halves and the window resets or is cut.

TCP three-way handshake

The client sends SYN with a sequence number, the server replies SYN-ACK acknowledging it and sending its own, and the client sends ACK. This synchronizes sequence numbers in both directions.

CSMA/CD minimum frame

Minimum frame size equals twice the propagation delay times bandwidth, so a collision is detected before transmission ends. For classic Ethernet this is 64 bytes including header and checksum.

Subnet host count

For a subnet with prefix length p, usable host addresses equal 2^(32 - p) - 2, subtracting the network and broadcast addresses. A /26 subnet therefore has 62 usable hosts.

Distance vector count-to-infinity

Distance-vector routing propagates stale routes because neighbors trust each other's advertised distances. Split horizon, poison reverse, and triggered updates mitigate but do not eliminate the problem.

Deadlock four conditions

Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait simultaneously. Breaking any one condition prevents deadlock; Banker's algorithm avoids it by denying unsafe allocations.

Belady's anomaly

With FIFO page replacement, increasing the number of frames can increase the number of page faults. LRU and Optimal replacement are stack algorithms and never exhibit this anomaly.

Thrashing definition

A system thrashes when it spends more time paging than executing because the sum of working sets exceeds physical memory. The working-set model and page-fault-frequency control are standard remedies.

Counting sort stability

Counting sort runs in O(n + k) for keys in range 0 to k-1 and is stable if the output is filled from the end using cumulative counts. It is not comparison based, so the n log n lower bound does not apply.

Catalan number trees

The number of distinct binary search tree shapes on n distinct keys is the Catalan number C_n = (1/(n+1))·C(2n,n), which grows as Θ(4^n / n^(3/2)).

Edit distance recurrence

Levenshtein distance uses D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + cost) where cost is 0 if characters match and 1 otherwise. It runs in O(mn) time.