The last practice set. Time yourself: 40 minutes is GATE pace for twelve questions of this mix.
⏱️
12 questions · 21 marks · 40 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.
Q1NAT1 markGeometric sum
1 + 2 + 4 + … + 1024 = ?
Numerical answer: ________
Q2MCQ1 markAmortised cost
A dynamic array doubles its capacity when full. The amortised cost of one append is:
- (A) Θ(√n)
- (B) Θ(n)
- (C) Θ(log n)
- (D) Θ(1)
Q3MCQ2 marksChange of variable
T(n) = 2T(√n) + 1 solves to:
- (A) Θ(log n)
- (B) Θ(log log n)
- (C) Θ(log n · log log n)
- (D) Θ(√n)
Q4NAT2 marksDouble hashing
m = 11, h₁(k) = k mod 11, h₂(k) = 7 − (k mod 7), probe i at (h₁ + i·h₂) mod 11. Insert 27, 43, 692, 72. Slot of 692?
Numerical answer: ________
Q5NAT2 marksBubble sort
Bubble sort on [5, 1, 4, 2, 8]: total number of swaps?
Numerical answer: ________
Q6NAT2 marksRadix sort
LSD radix sort on [329, 457, 657, 839, 436, 720, 355]. After the second pass (tens digit), which number is third?
Numerical answer: ________
Q7NAT1 markFast power
Multiplications used by repeated squaring to compute x⁴⁵ (squarings plus one per odd step)?
Numerical answer: ________
Q8NAT2 marksActivity selection
Activities (start, finish): (1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10), (9, 11), (11, 14), (13, 16). Maximum number of non-overlapping activities?
Numerical answer: ________
Q9NAT2 marks0/1 knapsack
Items (weight, value): (4, 10), (3, 8), (2, 6), (5, 12); capacity 9. Maximum value?
Numerical answer: ________
Q10NAT2 marksEdit distance
Edit distance between intention and execution?
Numerical answer: ________
Q11NAT2 marksKruskal
Undirected graph: P–Q 2, P–R 3, Q–R 1, Q–S 4, R–S 5, R–T 6, S–T 2. MST weight?
Numerical answer: ________
Q12NAT2 marksFloyd–Warshall
Directed graph on 1–3: 1→2 4, 1→3 11, 2→1 6, 2→3 2, 3→1 3. Final D[1][3]?
Numerical answer: ________
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 20471 mark
2¹¹ − 1.
Re-read: Lesson 0.1.2 — Math toolkit: logarithms, floors and ceilings, sums (arithmetic, geometric, harmonic)
Q2 Answer: (D)1 mark
Total copies stay below 2n.
- (A) is wrong: No.
- (B) is wrong: That is one worst-case append.
- (C) is wrong: No.
Re-read: Lesson 1.3.1 — Best, worst and average case; space complexity and recursion depth; amortised cost
Q3 Answer: (A)2 marks
m = log n: S(m) = 2S(m/2) + 1 = Θ(m).
- (B) is wrong: That is T(√n) + 1.
- (C) is wrong: That needs + log n.
- (D) is wrong: No.
Re-read: Lesson 1.2.4 — Harder recurrences: change of variables, T(n−1) forms, unequal splits
Q4 Answer: 02 marks
h₁ = 10 is taken by 43; h₂ = 7 − 6 = 1; (10 + 1) mod 11 = 0.
Re-read: Lesson 2.2.2 — Open addressing: linear probing, quadratic probing, double hashing
Q5 Answer: 42 marks
Swaps = inversions: (5,1), (5,4), (5,2), (4,2).
Re-read: Lesson 3.1.1 — Bubble sort and selection sort: passes, comparisons, swaps
Q6 Answer: 4362 marks
After units: 720, 355, 436, 457, 657, 329, 839; after tens: 720, 329, 436, 839, 355, 457, 657.
Re-read: Lesson 3.3.2 — Counting sort, radix sort and bucket sort
Q7 Answer: 81 mark
45 = 101101₂: 5 squarings + 3 extra.
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q8 Answer: 42 marks
(1, 3), (4, 7), (8, 10), (11, 14).
Re-read: Lesson 4.2.1 — The greedy method; activity selection
Q9 Answer: 242 marks
(4, 10) + (3, 8) + (2, 6) weigh 9.
Re-read: Lesson 5.1.2 — 0/1 knapsack
Q10 Answer: 52 marks
Substitute the first five letters i, n, t, e, n by e, x, e, c, u; the ending tion already matches.
Re-read: Lesson 5.2.3 — Longest increasing subsequence, edit distance and other sequence DPs
Q11 Answer: 92 marks
Q–R 1, P–Q 2, S–T 2, Q–S 4.
Re-read: Lesson 6.2.2 — Kruskal's algorithm and union–find
Q12 Answer: 62 marks
1 → 2 → 3 = 4 + 2.
Re-read: Lesson 6.3.3 — All-pairs shortest paths: Floyd–Warshall