Understanding when to apply a given ADT or design pattern is the core skill of applied algorithmics. This requires knowing not just what each ADT/pattern does, but its strengths, weaknesses, and the problem characteristics that make it suitable.
KEY TAKEAWAY: Selecting an appropriate ADT and design pattern requires matching the requirements of the problem with the operations and complexity of available tools.
| ADT | Core Characteristic | Best Applied When |
|---|---|---|
| Set | Uniqueness, membership testing | Need to track which items have been seen; set operations (union, intersection) |
| List | Ordered sequence, dynamic size | Order matters; duplicates allowed; sequential processing |
| Array | Direct indexed access, fixed size | Need $O(1)$ random access; size known upfront; DP tables |
| Dictionary | Key-value lookup, fast retrieval | Need to map one thing to another; lookup by identifier |
| Stack | LIFO access | Undo/redo; DFS; backtracking; function call tracking |
| Queue | FIFO access | BFS; scheduling; simulating arrival processes |
| Priority Queue | Priority-based access | Greedy algorithms (Prim’s, Dijkstra’s); simulation; scheduling by urgency |
| Graph | Relationship modelling | Networks, dependencies, connectivity problems |
| Tree | Hierarchical structure | Hierarchies, decision trees, spanning trees |
| Pattern | Strategy | Best Applied When |
|---|---|---|
| Brute-force | Try all possibilities | Small inputs; no efficient algorithm known; correctness critical |
| Greedy | Make locally optimal choices | Greedy choice property holds; optimal substructure |
| Divide and conquer | Split, solve, merge | Problem can be split into independent subproblems |
| Dynamic programming | Memoise overlapping subproblems | Subproblems overlap; optimal substructure |
| Backtracking | Depth-first + pruning | Constraint satisfaction; search with elimination |
| Heuristics | Approximate solutions | NP-Hard problems; good enough solution acceptable |
Indicators for each pattern:
When evaluating whether an algorithm is “fit for purpose”, consider:
1. Correctness: Does it always produce the right answer?
2. Efficiency: Is the time/space complexity acceptable for the expected input size?
3. Scalability: How does it perform as input grows?
4. Simplicity: Is it easy to implement and verify?
EXAM TIP: VCAA questions often present a scenario and ask you to select and justify an ADT and design pattern. Address: (1) what operations the problem requires, (2) which ADT supports those operations efficiently, (3) which design pattern fits the problem structure.
