Twelve more mixed questions. Before computing, name the lesson each one comes from; that is the skill the exam tests.
⏱️
12 questions · 20 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.
Q1MCQ1 markOrdering functions
Arrange by increasing growth: f₁ = 2^(log n), f₂ = n log n, f₃ = n^(log n), f₄ = (log n)^(log n).
- (A) f₁, f₂, f₃, f₄
- (B) f₁, f₂, f₄, f₃
- (C) f₄, f₁, f₂, f₃
- (D) f₂, f₁, f₄, f₃
Q2NAT2 marksRecurrence value
T(1) = 1 and T(n) = T(n − 1) + n. T(20)?
Numerical answer: ________
Q3NAT1 markFirst occurrence
Sorted array (0-based) [1, 2, 2, 2, 3, 5, 5, 8]. A first-occurrence binary search for 5 returns which index?
Numerical answer: ________
Q4NAT1 markExpected probes
Open addressing with uniform hashing and load factor 0.75: upper bound on the expected probes of an unsuccessful search?
Numerical answer: ________
Q5NAT2 marksInsertion sort
Insertion sort on [4, 3, 2, 10, 12, 1, 5, 6]: total number of shifts (element moves one place right)?
Numerical answer: ________
Q6NAT2 marksMerge sort
Worst-case number of comparisons of merge sort on 8 elements?
Numerical answer: ________
Q7NAT1 markMin and max
Minimum number of comparisons that always suffice to find both the minimum and the maximum of 100 numbers?
Numerical answer: ________
Q8NAT2 marksJob sequencing
Unit-time jobs (deadline, profit): J1 (2, 60), J2 (1, 100), J3 (3, 20), J4 (2, 40), J5 (1, 20). Maximum profit?
Numerical answer: ________
Q9NAT2 marksCoin change
Number of ways to make 12 with coins {2, 3, 5} (order ignored)?
Numerical answer: ________
Q10NAT2 marksTopological orders
DAG: 1 → 2, 1 → 3, 2 → 4, 3 → 4, 4 → 5, 4 → 6. Number of topological orders?
Numerical answer: ________
Q11NAT2 marksDAG shortest paths
DAG: r→s 5, r→t 3, s→t 2, s→x 6, t→x 7, t→y 4, t→z 2, x→y −1, x→z 1, y→z −2. Shortest distance from r to z?
Numerical answer: ________
Q12MCQ2 marksStrassen
T(n) = 7T(n/2) + n² solves to:
- (A) Θ(n³)
- (B) Θ(n²)
- (C) Θ(n² log n)
- (D) Θ(n^(log₂ 7))
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: (B)1 mark
f₁ = n. Take logs: log n, log n + log log n, (log n)², log n · log log n.
- (A) is wrong: f₄ is below f₃ (log log n < log n).
- (C) is wrong: f₄ grows faster than any polynomial.
- (D) is wrong: f₁ = n is below n log n.
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q2 Answer: 2102 marks
1 + 2 + … + 20.
Re-read: Lesson 1.2.1 — Recurrences from recursive code; solving by unrolling (substitution)
Q3 Answer: 51 mark
The 5s occupy indices 5 and 6.
Re-read: Lesson 2.1.2 — Binary search variants and the Ω(log n) lower bound for searching
Q4 Answer: 41 mark
1 / (1 − 0.75).
Re-read: Lesson 2.2.3 — Expected probes and collision probabilities
Q5 Answer: 122 marks
Shifts = inversions = 12.
Re-read: Lesson 3.1.2 — Insertion sort and inversions; stable and in-place sorting
Q6 Answer: 172 marks
n log n − n + 1 = 24 − 8 + 1.
Re-read: Lesson 3.2.1 — Merge sort: merging, recurrence, comparison counts
Q7 Answer: 1481 mark
3n/2 − 2.
Re-read: Lesson 3.3.3 — Selection: minimum and maximum, second largest, k-th smallest
Q8 Answer: 1802 marks
J2 in slot 1, J1 in slot 2, J3 in slot 3.
Re-read: Lesson 4.2.2 — Fractional knapsack; job sequencing with deadlines
Q9 Answer: 52 marks
2×6; 2×3 + 3×2; 2 + 5 + 5; 2×2 + 3 + 5; 3×4.
Re-read: Lesson 5.2.2 — Subset sum, coin change and rod cutting
Q10 Answer: 42 marks
2 and 3 in either order; 5 and 6 in either order.
Re-read: Lesson 6.1.3 — Topological sort, cycle detection, connected and strongly connected components
Q11 Answer: 52 marks
r→t→z = 3 + 2 (r→t→y→z also 5).
Re-read: Lesson 6.3.2 — Bellman–Ford, negative cycles, shortest paths in DAGs
Q12 Answer: (D)2 marks
log₂ 7 ≈ 2.81 > 2: leaves dominate.
- (A) is wrong: That is 8 subproblems.
- (B) is wrong: Ignores the 7 subproblems.
- (C) is wrong: Would need equal levels.
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)