GATE Algorithms questions come back in a small number of shapes. For each shape: the cue in the question, the fastest method, and the lesson that teaches it.
| # | Pattern (cue) | Fastest method | Lesson |
|---|---|---|---|
| 1 | "value of count after the loops" | count each loop's trips: ×2 → log, ×k → log_k, i² ≤ n → √n; dependent inner loops sum | Lesson 1.1.3 |
| 2 | "arrange in increasing order of growth" | take logs; ladder 1 < log log < log < n^ε < n < n log n < n² < 2ⁿ < n! | Lesson 1.1.2 |
| 3 | T(n) = aT(n/b) + f(n) | compare f with n^(log_b a); equal → × log | Lesson 1.2.3 |
| 4 | T(√n) or T(n − 1) forms | m = log n for roots; T(n − 1) + f → Σ f | Lesson 1.2.4 |
| 5 | value returned / number of calls | tabulate small n bottom-up; naive Fibonacci calls 2F(n+1) − 1 | Lesson 5.1.1 |
| 6 | binary-search probes | write lo, hi, mid each step; ≤ ⌊log n⌋ + 1 | Lesson 2.1.1 |
| 7 | final hash-table layout | trace insertions; probe count includes the home slot | Lesson 2.2.2 |
| 8 | expected probes / empty slots / collisions | 1/(1 − α); m(1 − 1/m)ⁿ; C(n, 2)/m | Lesson 2.2.3 |
| 9 | swaps, shifts, inversions | bubble swaps = insertion shifts = inversions | Lesson 3.1.2 |
| 10 | quicksort comparisons / worst case | Lomuto n − 1 per partition; sorted input with end pivot → Θ(n²) | Lesson 3.2.2 |
| 11 | heap after build / insert / delete | build from ⌊n/2⌋ down; insert sifts up; extract swaps root with last | Lesson 3.2.3 |
| 12 | minimum comparisons | max n − 1; min+max 3n/2 − 2; second largest n + ⌈log n⌉ − 2; sorting ⌈log n!⌉ | Lesson 3.3.3 |
| 13 | which sort is stable / in-place / best here | the stability and in-place lists; nearly sorted → insertion | Lesson 3.3.1 |
| 14 | Huffman length / average | merge two smallest; cost = Σ merges; average = cost / Σ f | Lesson 4.2.3 |
| 15 | greedy schedules / fractional knapsack | sort by finish; by profit with latest slot; by v/w | Lesson 4.2.2 |
| 16 | DP table entry (knapsack, LCS, edit) | fill only the needed rows; match → diagonal + 1 | Lesson 5.1.3 |
| 17 | matrix-chain cost | m[i][j] = min m[i][k] + m[k+1][j] + p_{i−1}p_kp_j by length | Lesson 5.2.1 |
| 18 | valid BFS / DFS orders | BFS: new neighbours as a block; DFS: next vertex adjacent to the deepest unfinished one | Lesson 6.1.1 |
| 19 | edge type from d/f times | nested intervals → tree/forward or back; disjoint → cross | Lesson 6.1.2 |
| 20 | number of topological orders | fix forced vertices, multiply independent choices | Lesson 6.1.3 |
| 21 | MST weight / count / which edge | Kruskal by hand; ties → count swaps; cycle and cut properties | Lesson 6.2.1 |
| 22 | Dijkstra order and distances | table of tentative distances; check for negative edges | Lesson 6.3.1 |
| 23 | complexity of a graph algorithm | BFS/DFS V + E; Kruskal E log E; Prim/Dijkstra V² or E log V; Bellman–Ford VE; Floyd V³ | Lesson 6.3.2 |
⏱️
Time budget in the exam
1-mark questions: under 90 seconds. 2-mark questions: under 3 minutes. If a trace is taking longer, you have not yet drawn the table (queue, heap array, DP grid or distance row) that the question is really about.
⏱️
8 questions · 16 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1NAT2 marksPattern 1
for (i = 1; i <= 64; i++) for (j = 1; j <= 64; j = j * 2) count++; starting from count = 0. Final count?
Numerical answer: ________
Q2MCQ2 marksPattern 3
T(n) = 3T(n/4) + n log n solves to:
- (A) Θ(n^(log₄ 3))
- (B) Θ(n)
- (C) Θ(n log n)
- (D) Θ(n log² n)
Q3NAT2 marksPattern 7
m = 7, h(k) = k mod 7, quadratic probing (h + i²) mod 7. Insert 50, 700, 76, 85, 92, 73, 101. Slot of 101?
Numerical answer: ________
Q4NAT2 marksPattern 11
Insert 10, 20, 15, 30, 40 one at a time into an empty max-heap (sift up). Total number of swaps?
Numerical answer: ________
Q5NAT2 marksPattern 14
Frequencies a 5, b 9, c 12, d 13, e 16, f 45 (out of 100). Average Huffman code length (2 decimals)?
Numerical answer: ________
Q6NAT2 marksPattern 16
LCS length of AXYT and AYZX?
Numerical answer: ________
Q7MCQ2 marksPattern 19
DFS of a directed graph gives d/f times p 1/10, q 2/5, r 6/9. Edge r → q is explored. Its type?
- (A) Forward
- (B) Cross
- (C) Back
- (D) Tree
Q8NAT2 marksPattern 21
Square a–b–c–d–a with every side weight 1, plus diagonal a–c of weight 2. How many MSTs?
Numerical answer: ________
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 4482 marks
64 × 7 (j = 1, 2, 4, …, 64).
Re-read: Lesson 1.1.3 — Analysing loops: nested, dependent and logarithmic loops
Q2 Answer: (C)2 marks
n^(log₄ 3) ≈ n^0.79 is polynomially smaller than f: f dominates.
- (A) is wrong: That is when the leaves dominate.
- (B) is wrong: Drops the log factor.
- (D) is wrong: That is the equal case with f = w log n.
Re-read: Lesson 1.2.3 — The master theorem
Q3 Answer: 42 marks
101 mod 7 = 3 is held by 73; (3 + 1) mod 7 = 4 is free.
Re-read: Lesson 2.2.2 — Open addressing: linear probing, quadratic probing, double hashing
Q4 Answer: 52 marks
0 + 1 + 0 + 2 + 2; final heap [40, 30, 15, 10, 20].
Re-read: Lesson 3.2.3 — Heapsort: build-heap in O(n), heapify, extract-max
Q5 Answer: 2.242 marks
Merges 14, 25, 30, 55, 100 sum to 224.
Re-read: Lesson 4.2.3 — Huffman coding
Q6 Answer: 22 marks
AY or AX.
Re-read: Lesson 5.1.3 — Longest common subsequence
Q7 Answer: (B)2 marks
[2, 5] and [6, 9] are disjoint and q finished first.
- (A) is wrong: q is not a descendant of r.
- (C) is wrong: q is not an ancestor of r.
- (D) is wrong: q was already black.
Re-read: Lesson 6.1.2 — Depth-first search: discovery and finish times, edge classification
Q8 Answer: 42 marks
Any 3 of the 4 sides; the diagonal is the heaviest on its cycles.
Re-read: Lesson 6.2.1 — Minimum spanning trees: cut and cycle properties, uniqueness