Twelve questions from all phases, mixed on purpose so you must first recognise which idea each needs. Conventions as in the front matter: log = log₂, ascending sorts, key comparisons only, 1-based heaps, alphabetical adjacency lists.
⏱️
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 markLoop count
count = 0; for (i = 1; i < 1000; i = i * 3) count++; Final value of count?
Numerical answer: ________
Q2MCQ1 markMaster theorem
T(n) = 4T(n/2) + n² solves to:
- (A) Θ(n log n)
- (B) Θ(n² log n)
- (C) Θ(n³)
- (D) Θ(n²)
Q3NAT2 marksBinary search
Sorted array (0-based) [3, 8, 12, 17, 21, 25, 30, 34, 39, 42, 48, 53, 57, 61, 66]. Iterative binary search with mid = ⌊(lo + hi)/2⌋ for 30: how many array elements are compared with 30?
Numerical answer: ________
Q4NAT2 marksLinear probing
Table of size 10, h(k) = k mod 10, linear probing. Insert 12, 18, 13, 2, 3, 23, 5, 15 in that order. In which slot does 15 end up?
Numerical answer: ________
Q5NAT2 marksQuicksort
Quicksort with Lomuto partition (pivot = last element) on [2, 8, 7, 1, 3, 5, 6, 4]. Total number of key comparisons?
Numerical answer: ________
Q6NAT2 marksBuild-heap
Bottom-up build-max-heap on [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] (1-based). How many swaps?
Numerical answer: ________
Q7MCQ1 markChoosing a sort
Which algorithm is stable and runs in Θ(n log n) in the worst case?
- (A) Heapsort
- (B) Insertion sort
- (C) Quicksort
- (D) Merge sort
Q8NAT2 marksHuffman
Frequencies p 1, q 1, r 2, s 3, t 5, u 8. Average Huffman code length in bits per symbol (2 decimals)?
Numerical answer: ________
Q9NAT2 marksLCS
Length of the longest common subsequence of ABAZDC and BACBAD?
Numerical answer: ________
Q10NAT2 marksMatrix chain
Dimensions p = (5, 4, 6, 2, 7). Minimum scalar multiplications?
Numerical answer: ________
Q11NAT2 marksDijkstra
Directed graph: s→a 10, s→c 5, a→b 1, a→c 2, c→a 3, c→b 9, c→d 2, b→d 4, d→b 6, d→s 7. Dijkstra from s: distance to b?
Numerical answer: ________
Q12MSQ2 marksMST and paths
Which are true for a connected undirected graph with positive, distinct edge weights?
- (A) The MST is unique.
- (B) Doubling every weight leaves the MST unchanged.
- (C) The lightest edge is in the MST.
- (D) The heaviest edge is never in the MST.
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 71 mark
i = 1, 3, 9, 27, 81, 243, 729.
Re-read: Lesson 1.1.3 — Analysing loops: nested, dependent and logarithmic loops
Q2 Answer: (B)1 mark
w = n^(log₂ 4) = n² equals f: multiply by log n.
- (A) is wrong: Too small.
- (C) is wrong: Would need a = 8.
- (D) is wrong: Misses the log factor of the equal case.
Re-read: Lesson 1.2.3 — The master theorem
Q3 Answer: 42 marks
34 (mid 7), 17 (mid 3), 25 (mid 5), 30 (mid 6).
Re-read: Lesson 2.1.1 — Linear search and binary search: comparisons and correctness
Q4 Answer: 92 marks
Slots 2–8 are full (12, 13, 2, 3, 23, 5, 18) when 15 arrives at slot 5; it probes 5, 6, 7, 8 and lands in 9.
Re-read: Lesson 2.2.2 — Open addressing: linear probing, quadratic probing, double hashing
Q5 Answer: 152 marks
Pivot 4: 7; [2, 1, 3]: 2, then [2, 1]: 1; [7, 5, 6, 8]: 3, then [7, 5, 6]: 2.
Re-read: Lesson 3.2.2 — Quicksort: partitioning, best, worst and average cases
Q6 Answer: 72 marks
Final heap [16, 14, 10, 8, 7, 9, 3, 2, 4, 1].
Re-read: Lesson 3.2.3 — Heapsort: build-heap in O(n), heapify, extract-max
Q7 Answer: (D)1 mark
Merge sort is both.
- (A) is wrong: Not stable.
- (B) is wrong: Θ(n²) worst.
- (C) is wrong: Θ(n²) worst, not stable.
Re-read: Lesson 3.3.1 — The Ω(n log n) lower bound for comparison sorting; comparing all sorts
Q8 Answer: 2.252 marks
Merges 2, 4, 7, 12, 20 sum to 45; 45 / 20.
Re-read: Lesson 4.2.3 — Huffman coding
Q9 Answer: 42 marks
ABAD.
Re-read: Lesson 5.1.3 — Longest common subsequence
Q10 Answer: 1582 marks
(A₁(A₂A₃))A₄: 4·6·2 + 5·4·2 + 5·2·7 = 48 + 40 + 70.
Re-read: Lesson 5.2.1 — Matrix-chain multiplication
Q11 Answer: 92 marks
s→c→a→b = 5 + 3 + 1.
Re-read: Lesson 6.3.1 — Relaxation and Dijkstra's algorithm
Q12 Answer: (A) (B) (C)2 marks
The heaviest edge may be a bridge, which every spanning tree needs.
- (D) is wrong: A bridge is in every spanning tree, however heavy.
Re-read: Lesson 6.2.1 — Minimum spanning trees: cut and cycle properties, uniqueness