GATE CS Revision Notes: High-Yield Topics and Formulas
The GATE 2026 CS paper is done — GATE 2027 is the live cycle, with the exam on 6, 7, 13, 14, 20 and 21 February 2027. Treat this as a reference and follow the GATE CS 2027 study plan. Syllabus, key dates, topic quizzes, and previous-year papers live on the GATE CS prep hub.
If you already know the syllabus and need a fast recall sheet before a mock or the real paper, use this page. It is not a first-time course — for that, start from the GATE CS prep hub and the 2027 subject-wise study plan.
What follows is what usually shows up as 1–2 mark questions you can lose by forgetting a definition or a complexity, plus the traps that show up every year.
Engineering Mathematics
Linear algebra
- Matrix product:
(AB)ᵢⱼ = Σₖ Aᵢₖ Bₖⱼ det(AB) = det(A)·det(B);det(A⁻¹) = 1/det(A)when A is invertible- Eigenvalues:
det(A − λI) = 0; sum of eigenvalues = trace; product = determinant - Rank ≤ min(rows, columns); full rank means the matrix is invertible (square case)
Common trap: mixing row-rank with nullity. Rank–nullity: rank(A) + nullity(A) = number of columns.
Probability
P(A ∪ B) = P(A) + P(B) − P(A ∩ B)- Conditional:
P(A|B) = P(A ∩ B) / P(B) - Bayes:
P(A|B) = P(B|A)·P(A) / P(B) - Binomial:
P(X = k) = C(n,k) pᵏ (1−p)ⁿ⁻ᵏ - Poisson:
P(X = k) = λᵏ e⁻λ / k! - Standardize a normal:
Z = (X − μ) / σ
Common trap: applying Bayes without writing the total-probability denominator.
Discrete math (high yield)
P(n,r) = n! / (n−r)!,C(n,r) = n! / (r!(n−r)!)- Handshaking lemma:
Σ deg(v) = 2|E| - Tree on n vertices: exactly
n − 1edges, connected, acyclic Kₙhasn(n−1)/2edges
Digital Logic
- Identity / complement:
A + 0 = A,A·1 = A,A + A' = 1,A·A' = 0 - De Morgan:
(A + B)' = A'·B',(A·B)' = A' + B' - Absorption:
A + AB = A,A + A'B = A + B - Consensus:
AB + A'C + BC = AB + A'C - XOR:
A ⊕ B = A'B + AB';A ⊕ A = 0;A ⊕ 0 = A - NAND / NOR are universal; any function can be built from either alone
- 2's complement of B: invert bits, add 1 — used for
A − B
GATE angle: K-map minimization (SOP/POS) and flip-flop excitation tables show up more often than "name the gate."
Programming and Data Structures
Complexities you should recite cold
| Structure / op | Typical cost |
|---|---|
| Array access | O(1) |
| Unsorted array search | O(n) |
| Insert/delete mid-array | O(n) |
| Linked-list search | O(n) |
| Insert at head (linked list) | O(1) |
| Stack / queue push–pop | O(1) amortized |
| Balanced BST search | O(log n) |
| Hash table average search | O(1) average; O(n) worst |
Trees and graphs
- Max nodes at level i (root = 0):
2ⁱ - Perfect binary tree height h:
2ʰ − 1nodes - Min height for n nodes:
⌈log₂(n+1)⌉ - BST: left < root < right; inorder is sorted
- Adjacency matrix: O(V²) space, O(1) edge query
- Adjacency list: O(V+E) space, O(degree) edge query
GATE angle: you will be asked to trace C code — recursion stack, pointers, ++ side effects — not to write a full program. Practice on paper.
Algorithms
Sorting (memorize the table)
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Graph algorithms
- BFS / DFS: O(V + E); BFS = shortest path in unweighted graphs
- Dijkstra: non-negative weights; O((V+E) log V) with a heap
- Bellman–Ford: O(VE); handles negative edges; detects negative cycles
- Master theorem for
T(n) = aT(n/b) + f(n)— comparef(n)ton^(log_b a)
Common trap: running Dijkstra on a graph with negative edges because "it usually works."
Operating Systems
Scheduling
- FCFS: simple; convoy effect
- SJF: best average waiting time if burst times known; starvation risk
- Round robin: time quantum; response time vs overhead trade-off
- Priority: starvation unless aging
Memory
- FIFO page replacement can show Belady's anomaly
- LRU: replace least recently used; strong exam favourite
- Optimal: replace the page used farthest in the future (theoretical bound)
Deadlock
Four necessary conditions: mutual exclusion, hold-and-wait, no preemption, circular wait. Break any one to prevent deadlock. Banker's algorithm is avoidance, not detection.
DBMS
- 1NF: atomic attributes
- 2NF: 1NF + no partial dependency on a composite key
- 3NF: 2NF + no transitive dependency
- BCNF: every determinant is a candidate key
- ACID: atomicity, consistency, isolation, durability
- Joins: INNER keeps matches; LEFT/RIGHT keep the outer side; FULL keeps both
Common trap: calling a schema 3NF when a non-prime attribute determines another non-prime attribute.
Computer Networks
OSI reminder (physical → application): Physical, Data Link, Network, Transport, Session, Presentation, Application.
- TCP: connection-oriented, reliable, ordered; flow + congestion control
- UDP: connectionless, lower overhead, no delivery guarantee
- HTTP typically port 80 (HTTPS 443); request–response, application layer
GATE angle: fragmentation math, stop-and-wait / sliding-window utilization, and "which layer owns X" beat memorizing the pizza mnemonic alone.
What to revise the night before
- Sorting + BFS/DFS/Dijkstra complexities
- Deadlock conditions + one page-replacement walkthrough
- Normal forms + one join query you can write from scratch
- De Morgan + one 2's-complement subtraction
- Bayes + one eigenvalue/trace question
Then sleep. New topics on exam eve cost more marks than they gain.
For timed practice, use the GATE subject quizzes. For how marks actually distribute across years, read the PYQ topic-wise analysis.