GATE CS cheat sheet

Asymptotics: if lim f/g = c with 0 < c < ∞ then f = Θ(g); c = 0 gives f = O(g) and f = o(g); c = ∞ gives f = ω(g). Master theorem applies to T(n) = aT(n/b) + f(n): compare f(n) with n^(log_b a) to pick Θ(n^(log_b a)), Θ(n^(log_b a) log n), or Θ(f(n)) with regularity condition.

Sorting bounds: comparison sorts need Ω(n log n) worst-case; merge sort and heapsort give O(n log n) worst case, quicksort gives O(n log n) expected and O(n^2) worst. Counting/radix sort run in O(n + k) and O(d(n + b)) but are not comparison based and are stable only if the inner sort is stable.

Graph algorithms: Dijkstra with binary heap is O((V+E) log V) and fails on negative edges; Bellman-Ford is O(VE) and detects negative cycles; Floyd-Warshall is O(V^3) all-pairs; Kruskal is O(E log E) with union-find, Prim O(E log V) with a heap. BFS gives shortest paths in unweighted graphs, DFS gives topological order on a DAG.

Trees and hashing: a binary tree with n nodes has n+1 null pointers; a full binary tree with L leaves has 2L-1 nodes; height of a balanced BST is O(log n). Open addressing load factor α must stay below 1; expected probes for successful search are about 1/(1-α) for linear probing and -ln(1-α)/α for uniform hashing.

Dynamic programming and greedy: DP needs optimal substructure plus overlapping subproblems; greedy needs the greedy-choice property plus optimal substructure. LCS and edit distance are O(mn) time and space; 0/1 knapsack is O(nW) pseudo-polynomial; fractional knapsack is greedy by value/weight ratio and is optimal.

Recurrences and counting: number of binary trees on n nodes is Catalan C_n = (1/(n+1))·C(2n,n); number of labeled trees on n vertices is n^(n-2) (Cayley). Recurrences of the form T(n) = T(n-1) + n give Θ(n^2); T(n) = 2T(n/2) + n gives Θ(n log n); T(n) = 2T(n-1) + 1 gives Θ(2^n).

NP theory: P ⊆ NP ⊆ PSPACE; if any NP-complete problem is in P then P = NP. To prove X NP-complete, show X ∈ NP and reduce a known NP-complete problem to X in polynomial time (Cook-Levin: SAT is NP-complete). Halting problem and its complement are undecidable and recursively enumerable only for the halting set.

Operating systems: page fault handling uses FIFO, LRU, or Optimal replacement; Belady's anomaly affects FIFO only. Banker's algorithm checks safe state via need = max - allocation; deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait simultaneously. Semaphore P decrements and blocks at zero, V increments and wakes a waiter.

Digital logic: any Boolean function can be built from NAND or NOR alone. A 2^n-to-1 multiplexer implements any n-variable function; a full adder has sum = A⊕B⊕Cin and Cout = AB + Cin(A⊕B). Setup plus hold time constraints bound maximum clock frequency: T ≥ t_clk-to-q + t_comb + t_setup.

CPU performance: CPU time = IC × CPI × clock period; speedup = 1 / ((1-f) + f/s) by Amdahl's law. Pipeline speedup is limited by the longest stage plus pipeline register overhead; k-stage pipeline with n instructions takes k + (n-1) cycles ignoring hazards. Cache AMAT = hit time + miss rate × miss penalty.

Databases: 1NF requires atomic attributes, 2NF removes partial dependencies on a candidate key, 3NF removes transitive dependencies, BCNF requires every nontrivial FD's left side be a superkey. A relation in 3NF but not BCNF loses dependency preservation when decomposed to BCNF. Relational algebra: σ selects rows, π projects columns, ⋈ joins.

Transactions and concurrency: ACID properties; two-phase locking guarantees serializability but not freedom from deadlock; strict 2PL prevents cascading rollback. Conflict serializability is tested by building a precedence graph - acyclic means conflict serializable. Recoverable schedules require no read of uncommitted data before commit.

Networks: IPv4 header is 20 bytes minimum; TCP header is 20 bytes minimum; UDP header is 8 bytes. Sliding window throughput ≤ window size / RTT. CSMA/CD minimum frame size = 2 × propagation delay × bandwidth. Subnetting: hosts per subnet = 2^(32-prefix) - 2.

TCP and routing: TCP uses three-way handshake (SYN, SYN-ACK, ACK) and congestion control with slow start (exponential), congestion avoidance (additive increase), and multiplicative decrease on loss. Dijkstra and link-state (OSPF) compute shortest paths; distance-vector (RIP) uses Bellman-Ford and suffers count-to-infinity.

Theory of computation: a DFA has no ε-transitions; an NFA with n states converts to a DFA with at most 2^n states. Regular languages are closed under union, intersection, complement, and star but not under infinite intersection. Pumping lemma for regular languages: for long strings, xy^k z ∈ L with |xy| ≤ p and |y| ≥ 1.

Compiler and parsing: LL(1) grammars need no left recursion and disjoint FIRST/FOLLOW sets; LR parsers handle more grammars than LL. First(α) and Follow(A) drive predictive parsing tables. A grammar is ambiguous if some string has two distinct parse trees; operator precedence parsing uses precedence and associativity relations.