Divide and Conquer as a Design Method · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Split it, solve it, combine it

Computing · Algorithms & Data Structures · ages 18-20
Name ______________________   Date ____________

  1. When does the recursion stop?

    • When the pieces are small enough to solve directly
    • When the combine step is finished
    • When the input is split in half once

  2. Which order lists the three moves of divide and conquer?

    • Combine, split, solve
    • Split, solve, combine
    • Solve, combine, split

  3. If splitting is free and combining scans the pieces, the combine dominates.

    Circle one:   True   False

  4. One piece holds almost all the input, yet the split is free and the combine is cheap. Why can this still pay off?

    • The problem still shrinks every round while split and combine stay cheap
    • The larger piece counts as already solved
    • Free splits remove the need to combine

  5. A method splits for free, solves both halves the same way, and scans the halves to combine. Where does most of the work sit?

    • In the split
    • In the leaves
    • In the combine

  6. You split a task into 2 pieces, then split every piece into 2 again. How many pieces do you hold?

    Answer: ______________

  7. A friend must add up a long list with divide and conquer. Which plan follows the method?

    • Sort the list first, then add from largest to smallest
    • Add the numbers left to right in a single pass
    • Split the list, add each half the same way, then add the two sums

  8. A student rejects an uneven split without checking any costs. What is the mistake?

    • They skipped the cheap base case
    • They judged by symmetry instead of by total cost
    • They combined before splitting
LightMySky · lightmysky.comW1-mt_YITRNb-HTE-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Split it, solve it, combine it W1-mt_YITRNb-HTE-s1

  1. When the pieces are small enough to solve directly · Tiny pieces are solved directly, and that ends the recursion.
  2. Split, solve, combine · The method always runs split, then solve, then combine.
  3. True · A costly combine outweighs a free split.
  4. The problem still shrinks every round while split and combine stay cheap · Shrinking every round with cheap helpers beats a pretty split.
  5. In the combine · The scan in the combine outweighs the free split.
  6. 4 · Two rounds of doubling give 2 times 2 pieces.
  7. Split the list, add each half the same way, then add the two sums · Only that plan splits, recurses the same way, and combines.
  8. They judged by symmetry instead of by total cost · Symmetry never decides alone; total cost decides.
Worksheet · LightMySky