GATE CSE Formula Sheet: Key Formulas for Every Subject

This GATE CSE formula sheet collects key formulas that past GATE papers have tested repeatedly, grouped by subject, with the trap to watch for where it matters most. It is a free selection from the book's last-minute revision sheet. Use it to check your recall, then practise each formula on previous-year questions.

Key takeaways

• Many GATE CSE numerical questions reuse the same formulas with new numbers.
• A formula is only useful with its conventions: log base 2, powers of two for memory, 10^6 for Mbps unless stated.
• Many traps are off-by-one errors: (k + n − 1) cycles, 2^m − 1 windows, n(k − 1) + 1 resources.
• You cannot carry paper into the exam (confirm current rules at gate2027.iitm.ac.in), so formulas must be in memory.

How to read this sheet

Notation: log means log base 2 unless written ln; ceil(x) and floor(x) are ceiling and floor; C(n, k) is the binomial coefficient; x^y is x to the power y. For memory sizes, KB means 2^10 unless the question says otherwise; for data rates, Mbps means 10^6 bits per second unless stated.

Operating System

For how these formulas turn into questions, see Operating Systems for GATE CSE 2027.

Computer Organization and Architecture

• offset = log(B); sets = C / (k × B); index = log(sets); tag = A − index − offset (B block bytes, C cache bytes, k associativity, A address bits; fully associative has index = 0)
• AMAT = t1 + m1 × (t2 + m2 × (t3 + m3 × t_mem)) (local miss rates; add lower-level time only on a miss)
• Cycle tau = max stage delay + latch delay; T_pipe(n) = (k + n − 1) × tau; T_nonpipe(n) = n × sum of stage delays
• Branch: CPI = 1 + f_b × (1 − p) × penalty (f_b branch fraction, p predictor accuracy)
• Overflow flag = C_in XOR C_out of the MSB

Computer Networks

The patterns behind these are covered in Computer Networks for GATE CSE 2027.

Databases

• Internal node: p × ptr + (p − 1) × key ≤ B, so p = floor((B + key) / (ptr + key)); leaf: k × (key + recptr) + ptr ≤ B, so k = floor((B − ptr) / (key + recptr))
• Levels for N records with fan-out f: ceil(log_f N) (including leaves); block accesses = levels + 1 for the data block
• Super keys with one candidate key of size k over n attributes = 2^(n − k)
• Lossless binary decomposition iff (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 in F+; dependency preserving iff (F1 ∪ F2)+ = F+
• Interleavings of two transactions with m and n operations = C(m + n, m)

This page gives a selection. The book's last-minute revision sheet has full formula tables for all ten subjects, each row with symbols, when the formula applies and its typical trap, plus the top 50 concepts, the most-asked algorithms step by step, a traps table, edge cases and an exam-day checklist. It is part of the GATE CSE 2027 book.

Algorithms

• Standard recurrences, each result a Theta bound: T(n − 1) + n = n^2; T(n / 2) + 1 = log n; 2T(n / 2) + n = n log n; T(sqrt n) + 1 = log log n; T(n / 3) + T(2n / 3) + n = n log n
• Master theorem trap: 2T(n/2) + n log n is Case 2 with k = 1, so Theta(n log^2 n), not n log n
• Max and min together: ceil(3n / 2) − 2; second largest: n + ceil(log n) − 2; binary search worst: floor(log n) + 1 comparisons
• Catalan C_n = C(2n, n) / (n + 1): 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 for n = 0..10 (BSTs on n keys, stack permutations)
• Build-heap: floor(n / 2) sift-downs, at most 2n comparisons, Theta(n)

Discrete and Engineering Mathematics

• v − e + f = 2 (connected planar; f counts the outer face); e ≤ 3v − 6 (v ≥ 3); bipartite or triangle-free planar e ≤ 2v − 4
• Spanning trees: K_n has n^(n − 2); K_m,n has m^(n − 1) × n^(m − 1); C_n has n
• Relations: relations on an n-set: 2^(n^2); reflexive: 2^(n^2 − n); symmetric: 2^(n(n + 1)/2); reflexive and symmetric: 2^(n(n − 1)/2)
• Eigenvalues: sum = trace, product = det; A^k has lambda^k, A^-1 has 1/lambda, A + cI has lambda + c
• Bayes: P(A_i | B) = P(B | A_i) P(A_i) / sum_j P(B | A_j) P(A_j)
• Uniform(a, b): mean (a + b) / 2, variance (b − a)^2 / 12; Exponential(lambda): mean 1 / lambda, variance 1 / lambda^2

Digital Logic

• n-bit 2's complement range −2^(n − 1) .. 2^(n − 1) − 1
• IEEE-754 single: 1 sign, 8 exponent (bias 127), 23 fraction; value = (−1)^S × 1.F × 2^(E − 127) for 1 ≤ E ≤ 254
• Functions of n variables: 2^(2^n); self-dual: 2^(2^(n − 1))
• Counter: mod-N needs ceil(log N) flip-flops; ring counter with n flip-flops has n states, Johnson 2n

Theory of Computation

• #a ≡ r (mod p): p states; #a mod p and #b mod q independent: p × q
• Contains w as a substring: |w| + 1; ends with w: |w| + 1; starts with w: |w| + 2 (dead state); k-th symbol from the right is a: 2^k (NFA k + 1)
• NFA with n states: minimal DFA has at most 2^n states
• CNF derivation of a string of length n takes exactly 2n − 1 steps; GNF takes n

Compiler Design

• LR(0) items = sum over productions of (|RHS| + 1), including S' → S which contributes 2; an ε-production contributes 1
• LALR states = LR(0)/SLR states; merging can add only reduce–reduce conflicts
• live-in(B) = use(B) ∪ (live-out(B) − def(B)); live-out(B) = ∪ live-in(successors)
• Basic-block leaders: the first instruction; any jump target; any instruction immediately after a jump (conditional or unconditional)

Programming and Data Structures

• Row-major A[i][j] with bounds [l1..u1][l2..u2]: base + ((i − l1) × (u2 − l2 + 1) + (j − l2)) × w
• Full (strict) binary tree: L = I + 1, n = 2L − 1; k-ary strict tree: L = (k − 1) I + 1, n = k I + 1
• Heap (1-based): parent floor(i / 2), children 2i and 2i + 1; 0-based: parent floor((i − 1) / 2), children 2i + 1 and 2i + 2
• Binary tree of height h (edges): max nodes 2^(h + 1) − 1, min nodes h + 1

How to revise with a formula sheet

1. Read it daily in the final two weeks, and once more on the morning of the exam.
2. Attach a trap to every formula. Knowing (k + n − 1) is half the job; knowing that k × n is the classic wrong answer is the other half. Common mistakes that cost marks in GATE CSE lists the traps subject by subject.
3. Write the unit next to every number. ms versus µs versus ns, KB as 1,000 or 1,024, bits versus bytes. Unit slips are a common cause of wrong NAT answers.
4. Carry full precision. Round only the final answer, to the decimals the question asks for. The MCQ, MSQ and NAT strategy guide covers answer entry for each type.
5. Use the rough sheet early. In the first five minutes, write the few formulas you are most likely to forget under pressure, such as the effective access time formula, (k + n − 1), the Go-Back-N and Selective Repeat window limits, and the minimum-resources formula.

To place this inside a full revision schedule, follow the GATE CSE last-month revision plan.