GATE CY cheat sheet

Percentage change: successive changes of a% and b% give a net change of a + b + ab/100 percent; a 20% rise then 20% fall leaves a net 4% decrease.

Work-rate: if A alone takes a days and B alone takes b days, together they take ab/(a+b) days; the harmonic form generalizes to n workers.

Relative speed: same direction speed difference, opposite direction speed sum; a train of length L crossing a platform of length P covers L+P.

Boats: downstream speed = u+v, upstream = u-v; time ratio for equal distances is inverse of the speed ratio.

Simple interest = PRT/100; compound interest = P[(1+R/100)^T - 1]; CI exceeds SI by P(R/100)^2 for two years.

Permutations of a multiset with n1,n2,... identical items: n!/(n1!n2!...); circular arrangements of n distinct objects: (n-1)!.

P(A or B) = P(A) + P(B) - P(A and B); for independent events P(A and B) = P(A)P(B).

Data interpretation rule: compute the required ratio directly from the table rather than rounding each entry, to avoid compounding rounding error.

A relation on a set of n elements: at most 2^(n^2) relations, 2^(n^2-n) reflexive ones, and 2^(n^2-n)/2 symmetric ones.

Equivalence relation = reflexive + symmetric + transitive; partial order = reflexive + antisymmetric + transitive.

Handshaking lemma: sum of degrees = 2|E|; hence the number of odd-degree vertices is even.

A connected planar graph satisfies v - e + f = 2, and e <= 3v - 6 for simple planar graphs with v >= 3.

A tree on n vertices has exactly n-1 edges and is acyclic and connected; any two of these three properties imply the third.

Euler's formula for homogeneous functions: x du/dx + y du/dy = n u when u is homogeneous of degree n.

Rank-nullity: rank(A) + nullity(A) = number of columns; A is invertible iff rank equals order and det(A) != 0.

Eigenvalue facts: product of eigenvalues = det(A), sum = trace(A); symmetric real matrices have real eigenvalues and orthogonal eigenvectors.

Probability: Bayes' theorem P(A|B) = P(B|A)P(A)/P(B); for a Poisson variable mean = variance = lambda.

Boolean identities: A + A'B = A + B, and A + AB = A; consensus theorem AB + A'C + BC = AB + A'C.

NAND and NOR are functionally complete; any Boolean function can be built from NAND gates alone.

A 2^n-to-1 multiplexer realizes any n-variable function directly by tying inputs to 0 or 1.

n-bit ripple carry adder delay is proportional to n; carry lookahead reduces it to O(log n) using generate/propagate signals.

Setup and hold checks: data must be stable before the clock edge (setup) and after it (hold); hold violations cannot be fixed by slowing the clock.

A D flip-flop samples input at the active edge; a latch is level-sensitive and is transparent while enabled.

Karnaugh map grouping: groups of size 2^k, powers of two only, wrap around edges, and maximal groups give minimal SOP.

A Johnson counter with n flip-flops has 2n states; a ring counter has n states.

CPU time = instruction count x CPI x clock period; average CPI is the weighted sum over instruction classes.

Speedup from Amdahl's law: 1 / ((1-f) + f/s) where f is the enhanced fraction and s the improvement factor.

Cache AMAT = hit time + miss rate x miss penalty; splitting into L1 and L2 gives AMAT = t1 + m1(t2 + m2 x penalty).

Direct-mapped cache: block address maps to set (block mod number of sets); conflict misses vanish with full associativity but capacity misses remain.

Write-through keeps memory consistent but costs bandwidth; write-back needs a dirty bit and defers memory writes.

Pipelining ideal speedup equals number of stages; hazards are structural, data (forwarding or stalls), and control (branch prediction or flush).

IEEE 754 single precision: 1 sign bit, 8 exponent bits with bias 127, 23 fraction bits; double uses 11 exponent bits with bias 1023.

Little-endian stores the least significant byte at the lowest address; big-endian stores the most significant byte first.

C array indexing a[i] equals *(a+i); array names decay to pointers, but sizeof on an array yields the whole array size.

Pointer arithmetic scales by the pointed-to type; a pointer to int incremented by 1 advances sizeof(int) bytes.

A binary search tree with n nodes has expected height O(log n) but worst case O(n) when keys are inserted in sorted order.

A complete binary tree stored in an array of size n: children of index i are 2i+1 and 2i+2 (0-based), parent is floor((i-1)/2).

Stack is LIFO and queue is FIFO; a circular queue of capacity n distinguishes full from empty using a count or one unused slot.

Hash table with open addressing and load factor alpha: expected probes for linear probing grow as 1/(1-alpha).

Postfix evaluation uses one stack; converting infix to postfix uses a stack for operators and respects precedence and associativity.

In C, malloc returns void* and uninitialized memory; calloc zero-initializes; free must be applied exactly once per allocation.

Master theorem: T(n) = aT(n/b) + f(n); compare f(n) with n^(log_b a) to pick case 1, 2, or 3.

Merge sort is Theta(n log n) in all cases with O(n) extra space; quicksort averages O(n log n) but is O(n^2) on sorted input with a fixed pivot.

Dijkstra's algorithm requires non-negative edge weights; Bellman-Ford handles negative weights and detects negative cycles in O(VE).

Minimum spanning tree: Kruskal is O(E log E) using union-find; Prim is O(E log V) with a binary heap and suits dense graphs.

0/1 knapsack dynamic programming is O(nW) pseudo-polynomial; the fractional version is solved greedily by value/weight ratio.

Greedy choice works for interval scheduling by earliest finish time, Huffman coding, and fractional knapsack, but not for 0/1 knapsack.

NP-completeness: a problem is NP-complete if it is in NP and NP-hard; SAT, 3-SAT, clique, vertex cover, and Hamiltonian cycle are NP-complete.

Binary search on a sorted array of n elements takes at most floor(log2 n) + 1 comparisons; it requires random access and sorted order.

Regular languages are closed under union, intersection, complement, concatenation, and Kleene star; they are captured by DFA, NFA, and regular expressions.

Pumping lemma for regular languages: for a long enough string, some middle block can be repeated any number of times and stay in the language.

DFA with n states accepts an infinite language iff it has a reachable cycle on a path from start to an accepting state.

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

A language is recursive iff some Turing machine decides it; recursively enumerable iff some TM accepts it.

Halting problem is undecidable; by Rice's theorem any non-trivial semantic property of recursively enumerable languages is undecidable.

Myhill-Nerode: a language is regular iff its right-invariant equivalence relation has finitely many classes.

Pumping lemma for CFLs: z = uvwxy with |vwx| <= p and |vx| >= 1, and uv^i wx^i y in L for all i >= 0.

Phases in order: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, optimization, code generation.

Lexers use finite automata built from regular expressions; parsers use context-free grammars.

LL(1) parsing requires no left recursion and disjoint FIRST/FOLLOW sets for each nonterminal's alternatives.

LR parsing handles a larger class of grammars than LL; SLR, LALR, and canonical LR differ in lookahead computation.

An ambiguous grammar has a string with two distinct parse trees; left factoring removes common prefixes for predictive parsing.

Syntax-directed translation attaches attributes to grammar symbols; synthesized attributes flow up, inherited attributes flow down.

Three-address code uses temporaries and at most one operator per instruction; basic blocks are maximal straight-line sequences.

Common subexpression elimination, constant folding, and dead code elimination operate on the control flow graph; liveness analysis drives register allocation.

Process states: new, ready, running, waiting, terminated; a context switch saves and restores PCB state.

Necessary conditions for deadlock: mutual exclusion, hold and wait, no preemption, circular wait; breaking any one prevents deadlock.

Banker's algorithm is a deadlock avoidance scheme that checks whether a resource request leaves a safe state.

Semaphore P (wait) decrements and blocks at zero; V (signal) increments and wakes a waiter; a mutex is a binary semaphore.

Page table entries hold frame number plus valid, dirty, and reference bits; TLB hit avoids the extra memory access.

Page replacement: FIFO suffers Belady's anomaly, LRU does not; optimal replacement requires future knowledge.

Page fault effective access time = (1-p) x memory time + p x fault service time, where p is the fault rate.

Disk scheduling: SSTF minimizes seek but can starve; SCAN sweeps in one direction; C-SCAN wraps to the start for uniform wait.

Relational algebra operators: select, project, union, set difference, Cartesian product, rename, plus joins defined from these.

A relation is in 2NF if in 1NF and no non-prime attribute is partially dependent on a candidate key; 3NF forbids transitive dependency on a key.

BCNF: every non-trivial functional dependency has a superkey on its left side; 3NF permits dependencies on prime attributes.

Armstrong's axioms: reflexivity, augmentation, transitivity; derived rules include union, decomposition, and pseudotransitivity.

A schedule is conflict-serializable iff its precedence graph is acyclic; 2PL guarantees conflict serializability.

Two-phase locking has a growing and a shrinking phase; strict 2PL holds exclusive locks until commit and avoids cascading rollback.

SQL execution order: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY; HAVING filters groups while WHERE filters rows.

B+ tree of order m stores up to m-1 keys per node and keeps all data in leaves linked for range scans; height is O(log_m n).

OSI layers: physical, data link, network, transport, session, presentation, application; TCP/IP merges the top three into application.

Stop-and-wait efficiency = 1/(1+2a) where a = propagation delay / transmission time; sliding window efficiency approaches 1 when window >= 1+2a.

TCP uses a three-way handshake (SYN, SYN-ACK, ACK) and closes with FIN/ACK exchanges; it provides reliable ordered byte streams.

TCP congestion control: slow start doubles cwnd per RTT, congestion avoidance adds one MSS per RTT, and fast retransmit triggers on three duplicate ACKs.

IPv4 header is 20 bytes minimum; the TTL field is decremented at each router and the packet is dropped at zero.

Classless addressing: number of usable hosts in a /n block is 2^(32-n) - 2 after removing network and broadcast addresses.

CSMA/CD detects collisions and backs off exponentially; CSMA/CA avoids collisions with acknowledgements and is used in wireless LANs.

DNS resolution is iterative or recursive; ARP maps IP to MAC within a subnet, and a host sends to its default gateway for off-subnet traffic.