Lab 3 — Divide-and-Conquer Vector Sum (Sequential)

Classroom link

Purpose

You will implement a divide-and-conquer (D&C) summation algorithm for a large vector of integers. This lab focuses on:

  • Recursion and subproblem decomposition
  • A practical performance technique: a cutoff to avoid too much recursion overhead
  • Building confidence via correctness checks and benchmarking

What you’re given

A starter project that already includes:

  • A baseline sum (simple loop) that is correct and fast
  • A benchmark driver that:
    • Generates random integers
    • Runs multiple implementations
    • Checks that all results match the baseline
    • Prints average timings and speedups

Learning goals

By the end, you should be able to:

  1. Explain why divide-and-conquer can be slower than a simple loop if implemented naively.
  2. Implement a correct recursive D&C sum.
  3. Choose and justify a cutoff threshold.
  4. Use timing output to compare implementations.

Files you will edit

  • src/sum.cpp

You will implement:

  • sum_divide_conquer_seq(...)

Do not change:

  • Function signatures
  • The benchmark driver
  • The baseline implementation

Build and run

Linux

make
./vecsum_demo 5000000
./vecsum_demo 50000000 42

macOS (OpenMP enabled is fine even if you won’t use it yet)

brew install libomp
make
./vecsum_demo 5000000

If you get build errors on macOS, follow the starter README instructions (libomp + Makefile detection).

Step-by-step implementation instructions

Step 1: Understand the API and types

In src/sum.cpp, you’ll see:

  • using sum_t = ...; (some larger integer type to prevent overflow)
  • Functions that receive:
    • const std::vector<int>& a
    • indices lo (inclusive) and hi (exclusive)
    • a cutoff (or the project’s equivalent)

The core idea: sum the subarray a[lo..hi).

Step 2: Write the recursive structure

D&C for sum:

  • If the range is small: do a simple loop.
  • Otherwise:
    • Split the range in half
    • Recursively sum left half
    • Recursively sum right half
    • Return left + right

Pseudocode:

sum(a, lo, hi):
  n = hi - lo
  if n <= cutoff:
    s = 0
    for i in [lo, hi): s += a[i]
    return s
  mid = lo + n/2
  return sum(a, lo, mid) + sum(a, mid, hi)

Important details:

  • Use size_t or the project’s index type.
  • mid must be computed carefully: lo + (hi - lo)/2.
  • Use sum_t for accumulation.

Step 3: Choose a cutoff

If cutoff is too small, recursion overhead dominates and performance will be poor.
If cutoff is too large, you approach the baseline (which is fine, but you lose the point of D&C).

A reasonable starting point on modern systems is often something like:

  • 2,048 to 32,768 elements
  • You may tune it after you get correctness

Your code should use the passed-in cutoff (or the constant defined in the starter), not a hard-coded magic number unless instructed.

Step 4: Verify correctness

Run:

./vecsum_demo 5000000 42

The program should:

  • Print results for each method
  • Confirm they match baseline
  • Print timing comparisons

If your result differs, you likely have:

  • An off-by-one bug (hi exclusive vs inclusive)
  • Wrong mid computation
  • Using int instead of sum_t for the accumulator

What to submit

Push to GitHub Classroom:

  • src/sum.cpp with your implementation

No other files should be modified unless your instructor says so.

Hints (use if stuck)

Common correctness bugs:

  • Wrong base case condition: should be if (hi - lo <= cutoff) (or equivalent)
  • Using mid = (lo + hi)/2 is okay with size_t, but safer is lo + (hi - lo)/2
  • Loop bounds must match [lo, hi) exactly

Common performance “surprises”:

  • Baseline loop may beat your D&C version. That’s normal.
  • D&C adds function-call overhead and branch overhead.
  • The point is to build the structure that will later allow parallelism.

Grading rubric (Lab 3)

Total: 100 points

  1. Correctness (40)
  • 40: Always matches baseline on provided tests and large N
  • 25: Usually correct, fails edge case (small N, odd sizes, etc.)
  • 0: Incorrect results or crashes
  1. Proper D&C structure (25)
  • 25: Uses recursion, splits range, combines left+right correctly
  • 15: Mostly correct but flawed split/base-case structure
  • 0: Not D&C (just another loop)
  1. Cutoff base case (20)
  • 20: Uses cutoff properly to avoid recursion overhead
  • 10: Has a base case but not tied to cutoff / too frequent recursion
  • 0: No base case (or base case never triggers)
  1. Code quality (15)
  • 0: Hard to read, unsafe type usage, unnecessary changes elsewhere
  • 15: Clear variable names, consistent types, no unnecessary global state
  • 8: Works but messy or confusing

Scroll to Top