Phase 4 Checkpoint: 15 questions on divide and conquer and greedy algorithms.
⏱️
15 questions · 24 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 markPower
Multiplications to compute x⁸ by repeated squaring?
Numerical answer: ________
Q2NAT2 marksPower
Multiplications to compute x²⁰ with the recursive method?
Numerical answer: ________
Q3NAT2 marksMax subarray
Maximum subarray sum of [3, −4, 5, −1, 2, −6, 4]?
Numerical answer: ________
Q4MCQ1 markStrassen
Strassen's recurrence is:
- (A) T(n) = 8T(n/2) + n²
- (B) T(n) = 7T(n/2) + n
- (C) T(n) = 7T(n/2) + n²
- (D) T(n) = 3T(n/2) + n
Q5NAT1 markKaratsuba
Single-digit multiplications by Karatsuba for 64-digit numbers?
Numerical answer: ________
Q6NAT2 marksActivities
Activities (s, f): (1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9). Maximum compatible set size?
Numerical answer: ________
Q7MCQ1 markActivity rule
Greedy activity selection sorts activities by:
- (A) number of overlaps
- (B) duration
- (C) finish time
- (D) start time
Q8NAT2 marksFractional
Capacity 60; items (value, weight): (100, 20), (60, 10), (120, 40), (90, 30). Fractional knapsack value?
Numerical answer: ________
Q9NAT2 marksJobs
Jobs (deadline, profit): a (2, 100), b (1, 50), c (2, 10), d (1, 20), e (3, 30). Maximum profit?
Numerical answer: ________
Q10NAT2 marksHuffman
Frequencies 45, 13, 12, 16, 9, 5. Average Huffman codeword length (total 100)?
Numerical answer: ________
Q11NAT2 marksHuffman length
Frequencies p 5, q 25, r 7, s 15, t 4, u 12. Length of q's codeword?
Numerical answer: ________
Q12MCQ1 markPrefix codes
A prefix-free code with codeword lengths 1, 2, 3, 3 exists because:
- (A) the lengths sum to 9
- (B) 1/2 + 1/4 + 1/8 + 1/8 = 1 ≤ 1
- (C) any lengths work
- (D) the lengths are distinct
Q13NAT2 marksMerge
Optimal merge cost for files of sizes 3, 5, 9, 12, 15?
Numerical answer: ________
Q14NAT1 markCoins
Coins {1, 3, 4}, amount 6: minimum coins?
Numerical answer: ________
Q15MSQ2 marksParadigms
Which algorithms are greedy?
- (A) Huffman coding
- (B) Merge sort
- (C) Activity selection
- (D) Optimal merge pattern
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 31 mark
x², x⁴, x⁸.
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q2 Answer: 52 marks
20 → 10 → 5 → 2 → 1: 4 squarings + 1 odd step.
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q3 Answer: 62 marks
[5, −1, 2].
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q4 Answer: (C)1 mark
Seven half-size products, quadratic additions.
- (A) is wrong: Plain block method.
- (B) is wrong: Additions cost n².
- (D) is wrong: Karatsuba.
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)
Q5 Answer: 7291 mark
3⁶.
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)
Q6 Answer: 42 marks
(1, 2), (3, 4), (5, 7), (8, 9).
Re-read: Lesson 4.2.1 — The greedy method; activity selection
Q7 Answer: (C)1 mark
Earliest finish.
- (A) is wrong: Fails.
- (B) is wrong: Fails.
- (D) is wrong: Fails.
Re-read: Lesson 4.2.1 — The greedy method; activity selection
Q8 Answer: 2502 marks
Ratios 5, 6, 3, 3: take (60, 10) and (100, 20): 160 for 30 kg; the remaining 30 kg at ratio 3 give 90. Total 250.
Re-read: Lesson 4.2.2 — Fractional knapsack; job sequencing with deadlines
Q9 Answer: 1802 marks
a → 2, b → 1, e → 3.
Re-read: Lesson 4.2.2 — Fractional knapsack; job sequencing with deadlines
Q10 Answer: 2.242 marks
224 / 100.
Re-read: Lesson 4.2.3 — Huffman coding
Q11 Answer: 22 marks
q sits at depth 2.
Re-read: Lesson 4.2.3 — Huffman coding
Q12 Answer: (B)1 mark
Kraft's inequality: Σ 2^(−ℓ) ≤ 1.
- (A) is wrong: Irrelevant.
- (C) is wrong: {1, 1, 1} would fail.
- (D) is wrong: 3 is repeated.
Re-read: Lesson 4.2.3 — Huffman coding
Q13 Answer: 962 marks
3 + 5 = 8; 8 + 9 = 17; 12 + 15 = 27; 17 + 27 = 44: 8 + 17 + 27 + 44 = 96.
Re-read: Lesson 4.2.4 — Optimal merge pattern; when greedy fails
Q14 Answer: 21 mark
3 + 3.
Re-read: Lesson 4.2.4 — Optimal merge pattern; when greedy fails
Q15 Answer: (A) (C) (D)2 marks
Merge sort is divide and conquer.
- (B) is wrong: Not greedy.
Re-read: Lesson 4.2.4 — Optimal merge pattern; when greedy fails