Problem Decomposition, Correctness, and Testing Algorithms
How to break an unfamiliar problem into solvable pieces, what it actually means for an algorithm to be correct, and why edge cases decide whether it really is.
What you'll learn
- Break a stated problem into smaller, independently solvable subproblems
- Distinguish an algorithm that 'usually works' from one that is provably correct
- Identify the edge cases a solution must handle before writing any code
Explanation
Every algorithm problem gets more tractable once you separate three questions that are easy to blur together: what is being asked (the precise input/output contract), how you'll compute it (the algorithm), and why it's correct (an argument, not a hope). Skipping straight to code without pinning down the first question is the single most common reason a solution "mostly works" but fails on inputs the author never considered.
Decomposition means breaking an unfamiliar problem into smaller pieces you already know how to solve, then combining those pieces. "Find the two numbers in a list that sum to a target" decomposes into "for each number, can I quickly check whether (target - number) has already been seen?" — which reduces the original problem to a lookup problem, a piece you already have tools for (the collections you'll cover throughout this course). Recognizing that a new problem is really a disguised version of one you already know how to solve is a skill that improves specifically with deliberate practice across many problems, not a fixed talent.
An algorithm is correct if it produces the right output for every valid input, not just the ones you happened to try. A convincing correctness argument usually walks through: the general case (does the core logic actually do what's claimed?), the boundary cases (an empty input, a single-element input, the first/last position), and any input shape the problem statement allows but that's easy to forget (duplicate values, negative numbers, already-sorted input, all-identical values). Testing an algorithm means deliberately constructing inputs that exercise each of those categories — a test suite that only checks one "normal-looking" input tells you almost nothing about whether the algorithm is actually correct, only that it isn't obviously broken on that one case.
Example
A solution that looks correct at a glance but has an untested edge case -- and the fix.
// BROKEN for one important edge case -- can you spot it before running?
function firstAndLast(arr) {
return [arr[0], arr[arr.length - 1]];
}
console.log(firstAndLast([1, 2, 3])); // [1, 3] -- looks right
console.log(firstAndLast([])); // [undefined, undefined] -- is that the right answer, or a bug?
// The FIX starts with deciding, explicitly, what should happen for an empty array --
// before writing more code. There is no "obviously correct" default; it depends on the spec.Try it yourself
Decide what firstAndLast([]) SHOULD do (throw? return null? return [undefined, undefined]?), then implement your decision.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write isPalindrome(str) that returns true if str reads the same forwards and backwards, case-sensitively, with NO special-casing beyond the general algorithm -- it must handle the empty string and single-character strings correctly using the same logic as everything else (no early-return special case needed if your general algorithm is right).
Checks: correctly identifies a palindrome · correctly rejects a non-palindrome · handles the empty string edge case · handles the single-character edge case
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write findPairSummingTo(numbers, target) that returns true if any TWO DISTINCT positions in numbers sum to target, false otherwise. A single element cannot pair with itself unless it appears twice in the array. Handle an empty array and a single-element array correctly (both should return false).
Checks: finds a valid pair · correctly reports no pair exists · handles an empty array · a single element never pairs with itself · two equal values at different positions can form a valid pair
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Writing code before deciding what the answer should be for empty input, a single element, or duplicate values -- guessing an answer for these AFTER a bug report is far more error-prone than deciding upfront.
- Testing only one 'normal-looking' input and treating a passing result as proof of correctness -- a single passing test proves the algorithm isn't obviously broken, nothing more.
- Confusing 'I can't think of a case where this fails' with 'I have checked this is correct' -- a genuine correctness argument walks through the boundary and edge cases explicitly, rather than relying on not having thought of a counterexample yet.
Knowledge check
Takeaway
Pin down exactly what's being asked before writing code, look for a way to reduce the problem to one you already know how to solve, and treat boundary/edge cases as required test inputs, not optional afterthoughts.
Summary
Decomposition breaks a problem into pieces you already know how to solve. Correctness means right output for every valid input, argued through the general case plus boundary and edge cases. A test suite only tells you what it actually tested — untested inputs remain unknown.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.