Designing a Solution
Real algorithm design draws on every idea in this unit at once: choose a strategy, back it with the right data structures, argue correctness, and analyze complexity. The skill is knowing which tool the problem calls for.
A practical design workflow:
- Understand the problem precisely: the inputs, the required output, the constraints, and the edge cases. Restate it in your own words.
- Choose a strategy. Ask: does it decompose into independent halves (divide-and-conquer)? Overlapping subproblems (dynamic programming)? A locally-optimal choice that provably works (greedy)? Or a network to explore (graph traversal)? Sometimes a brute force is fine; sometimes it must be beaten.
- Pick data structures that make the strategy's hot operations fast — a heap for repeatedly taking the extreme, a hash table for keyed lookup, a sorted array for binary search.
- Argue correctness — a loop invariant, an exchange argument, or the structure of the recursion.
- Analyze complexity — time and space — and compare against the constraints. If it is too slow, revisit the strategy.
- Test with typical, edge, and adversarial inputs.
For example, "find the k most frequent words in a huge text": count with a hash table (), then select the top k with a heap of size k ( over distinct words) rather than fully sorting — a design that consciously combines a strategy (selection via heap) with the right structures, justified by its complexity.
The mature lesson: these techniques are not separate exam topics but an integrated design toolkit. A strong algorithmist moves fluidly among them, choosing and combining whatever the problem demands, always balancing correctness against efficiency.
Common pitfall: reaching for a complex technique (dynamic programming, an exotic data structure) when a simple approach meets the constraints — or, conversely, brute-forcing a problem whose size demands a better strategy. Good design matches the technique to the problem's actual size and structure, neither over- nor under-engineering.