Specifying a problem: input, output and steps
Before writing any code, describe the problem exactly. This is the specification.
- Input: what data we get, its type and limits (e.g. "n whole numbers, 1 ≤ n ≤ 1000").
- Output: what we must give back (e.g. "the largest of them").
- Conditions: what is true before (precondition) and after (postcondition).
Writing the steps
An algorithm is a finite list of clear steps that turns any valid input into the right output. Write it as:
- natural language: "Look at each number; if it is bigger than the best so far, remember it."
- a numbered step list: 1. best ← first number. 2. For each next number x: if x > best then best ← x. 3. Output best.
- pseudocode or a flowchart for more precision.
Test it by hand on small inputs, including tricky ones (all equal, negative numbers, only one number).
Top-down and bottom-up design
Top-down (stepwise refinement): start with the whole task, split it into a few big steps, then split each step again until each part is easy to code. Example: "Make a report card" → read marks → compute averages → assign grades → print.
Bottom-up: build and test small, reusable pieces first (a function that finds the maximum, one that sorts), then join them into the full program.
Real projects mix both: plan top-down, build and test bottom-up.
Divide and conquer, and the halving method
Divide and conquer has three moves: split the problem into smaller parts of the same kind, solve each part (often by recursion), combine the answers.
- Binary search (halving): in a sorted list, compare with the middle and throw away half. n items need about log₂ n checks: 16 → 4, 1 000 000 → 20.
- Merge sort: split the list in two, sort each half, merge them: O(n log n).
- Fast power: a⁸ = ((a²)²)²: 3 multiplications instead of 7.
- Finding a root by bisection: halve an interval where a function changes sign.
Greedy algorithms
A greedy algorithm makes the choice that looks best right now and never changes it.
- Making change with 50, 20, 10, 5, 2, 1: biggest coin first. Optimal for this kind of coin system.
- Choosing the most activities in a day: always pick the one that ends earliest. Optimal.
- Fractional knapsack: take items with the best value per kg first. Optimal.
But greedy is not always right: with coins 1, 3, 4, paying 6 greedily gives 4 + 1 + 1 (3 coins), while 3 + 3 uses 2. To trust a greedy method you must prove it, or test it against a sure method.
Dynamic programming and backtracking
Dynamic programming (DP)
When the same smaller problems repeat, solve each once and store the answer in a table. Fewest coins for amount a: best[a] = 1 + min(best[a - c]) over coins c ≤ a, starting from best[0] = 0. For coins 1, 3, 4: best = 0, 1, 2, 1, 1, 2, 2. Filling the table from small to large is bottom-up; recursion with a memory is top-down (memoization). See the separate Dynamic programming lesson for more.
Backtracking
Build a solution one choice at a time. If a choice breaks a rule or leads to a dead end, undo it and try the next option. Used for mazes, Sudoku, the N-queens puzzle and listing all subsets. It is a careful brute force: it skips whole branches that cannot work.
Brute force
Try every possible answer. Always correct, but often far too slow (2ⁿ subsets, n! orders).
Choosing a technique: correctness, efficiency and data structures
| Technique | Use when | Example | Typical time |
|---|---|---|---|
| Brute force | input is tiny | try all passwords of 3 digits | often 2ⁿ or n! |
| Divide and conquer | parts are independent | binary search, merge sort | O(log n), O(n log n) |
| Greedy | a best local choice is proven safe | activity selection, change | O(n log n) |
| Dynamic programming | subproblems repeat | coin change, shortest paths | size of table |
| Backtracking | search with rules | maze, Sudoku | exponential, but pruned |
Justify it
Correctness: show the algorithm always stops and gives the right output (a loop invariant, a proof, or tests on edge cases). Efficiency: count steps as n grows (Big O) and compare with other methods.
Data structures help
Arrays for tables (DP), stacks for backtracking (remember where to go back), queues for level-by-level search. A binary tree stores items so that each node has at most two children; in a binary search tree smaller keys go left and larger go right, so searching halves the work at each level, just like binary search.
Try it: coins and a guessing game
- Play the 1-100 guessing game with a friend. Always ask about the middle. Can you always win in 7 questions? (2⁷ = 128.)
- With coins 1, 3, 4, write the DP table for amounts 0 to 10 on paper. Where does greedy fail?
- Open the last 3D step. Try coins 1, 7, 10 and amount 14. Greedy gives 10 + 1 + 1 + 1 + 1; DP gives 7 + 7.
- Write a step list for "find the smallest number in a list" and test it on 5, 5, 5 and on one number.
Key formulas and definitions
- Specification = input + output + conditions
- Halving: about log₂ n steps (16 → 4, 1024 → 10)
- Coin DP: best[0] = 0; best[a] = 1 + min best[a - c]
- Divide and conquer = split + solve + combine
- Greedy is fast but must be proved optimal
Worked examples
1. Write a specification and a step list for finding the largest of n numbers.
Input: n ≥ 1 numbers. Output: the largest. Steps: 1. best ← first number. 2. For each other number x: if x > best, best ← x. 3. Output best. For 4, 9, 2, 7, 12, 5, 10, 3 the output is 12 after 7 comparisons.
2. How many questions does halving need to find a number from 1 to 1000?
Each question halves the range: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. That is 10 questions (2¹⁰ = 1024 ≥ 1000).
3. Pay 87 greedily with coins 50, 20, 10, 5, 2, 1.
50 (37 left), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 coins.
4. Fill the DP table for coins 1, 3, 4 up to amount 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Activities (start-end): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Choose the most activities that do not overlap.
Greedy by earliest end: A (ends 11), then C (starts 11, ends 13), then E (starts 13). 3 activities: A, C, E.
6. Plan top-down: a program that tells a class its average mark and the top student.
Level 1: read data → compute → print. Level 2: read names and marks into lists; compute total and average; find the maximum mark and its name; print both. Each piece is then coded and tested bottom-up.
Common mistakes
- Starting to code before stating the input and output. Many 'bugs' are really an unclear specification.
- Assuming greedy is always optimal. It works only when you can prove it (coins 1, 3, 4 break it).
- Using binary search on an unsorted list. Halving needs sorted data.
- Confusing DP with divide and conquer. DP is for overlapping subproblems you store; divide and conquer splits into independent parts.