Phase 5 Checkpoint: 15 questions on dynamic programming.
⏱️
15 questions · 25 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.
Q1NAT1 markNaive calls
Naive recursive fib(4) makes how many calls?
Numerical answer: ________
Q2MCQ1 markDP property
Dynamic programming is preferred over plain recursion when:
- (A) subproblems overlap
- (B) subproblems are independent
- (C) the input is sorted
- (D) a greedy choice is safe
Q3NAT2 marksGrid paths
Right/down paths from the top-left cell to the bottom-right cell of a 4 × 6 grid of cells?
Numerical answer: ________
Q4NAT2 marksKnapsack
Items (weight, value): (1, 1), (3, 4), (4, 5), (5, 7); capacity 7. Maximum value?
Numerical answer: ________
Q5NAT2 marksKnapsack
Items (weight, value): (2, 3), (3, 4), (4, 5), (5, 6); capacity 5. K[2][5] (first two items, capacity 5)?
Numerical answer: ________
Q6NAT2 marksLCS
LCS length of ABCDEF and ACBDFE?
Numerical answer: ________
Q7NAT2 marksLCS count
Number of distinct LCSs of ABCBDAB and BDCABA?
Numerical answer: ________
Q8NAT2 marksMatrix chain
Dimensions p = (2, 3, 4, 5). Minimum scalar multiplications?
Numerical answer: ________
Q9NAT1 markCatalan
Full parenthesisations of 4 matrices?
Numerical answer: ________
Q10MCQ1 markMatrix chain time
Time of the matrix-chain DP for n matrices:
- (A) Θ(n²)
- (B) Θ(n³)
- (C) Θ(n² log n)
- (D) Θ(4ⁿ)
Q11NAT2 marksCoin ways
Ways to make 5 with coins {1, 2, 5} (order ignored)?
Numerical answer: ________
Q12NAT2 marksMin coins
Minimum coins to make 6 with {1, 3, 4}?
Numerical answer: ________
Q13NAT2 marksRod
Rod prices (lengths 1–8): 1, 5, 8, 9, 10, 17, 17, 20. Maximum revenue for length 4?
Numerical answer: ________
Q14NAT2 marksEdit distance
Edit distance between kitten and sitting?
Numerical answer: ________
Q15NAT1 markLIS
LIS length of [3, 10, 2, 1, 20]?
Numerical answer: ________
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 91 mark
1 + calls(3) + calls(2) = 1 + 5 + 3.
Re-read: Lesson 5.1.1 — Overlapping subproblems: memoisation vs tabulation; counting calls
Q2 Answer: (A)1 mark
Stored answers are reused.
- (B) is wrong: Then D&C suffices.
- (C) is wrong: Irrelevant.
- (D) is wrong: Then greedy suffices.
Re-read: Lesson 5.1.1 — Overlapping subproblems: memoisation vs tabulation; counting calls
Q3 Answer: 562 marks
3 downs and 5 rights in any order: C(8, 3).
Re-read: Lesson 5.1.1 — Overlapping subproblems: memoisation vs tabulation; counting calls
Q4 Answer: 92 marks
(3, 4) + (4, 5).
Re-read: Lesson 5.1.2 — 0/1 knapsack
Q5 Answer: 72 marks
Both items fit.
Re-read: Lesson 5.1.2 — 0/1 knapsack
Q6 Answer: 42 marks
ABDE, ABDF, ACDE, ACDF.
Re-read: Lesson 5.1.3 — Longest common subsequence
Q7 Answer: 32 marks
BCAB, BCBA, BDAB.
Re-read: Lesson 5.1.3 — Longest common subsequence
Q8 Answer: 642 marks
(A₁A₂)A₃.
Re-read: Lesson 5.2.1 — Matrix-chain multiplication
Q9 Answer: 51 mark
C₃.
Re-read: Lesson 5.2.1 — Matrix-chain multiplication
Q10 Answer: (B)1 mark
n² entries × n splits.
- (A) is wrong: Ignores splits.
- (C) is wrong: No.
- (D) is wrong: Brute force grows like 4ⁿ/n^1.5.
Re-read: Lesson 5.2.1 — Matrix-chain multiplication
Q11 Answer: 42 marks
See the lesson table.
Re-read: Lesson 5.2.2 — Subset sum, coin change and rod cutting
Q12 Answer: 22 marks
3 + 3.
Re-read: Lesson 5.2.2 — Subset sum, coin change and rod cutting
Q13 Answer: 102 marks
2 + 2: 5 + 5.
Re-read: Lesson 5.2.2 — Subset sum, coin change and rod cutting
Q14 Answer: 32 marks
k→s, e→i, insert g.
Re-read: Lesson 5.2.3 — Longest increasing subsequence, edit distance and other sequence DPs
Q15 Answer: 31 mark
3, 10, 20.
Re-read: Lesson 5.2.3 — Longest increasing subsequence, edit distance and other sequence DPs