Suitability of ADTs and Algorithm Design Patterns for Problem Contexts

Framework for Assessing Suitability

When faced with a problem, assess suitability by asking:
1. What data needs to be stored? → Choose an ADT
2. How is the data accessed? → Which ADT operations match?
3. What is the problem structure? → Which design pattern applies?
4. What are the constraints? → Does complexity fit the input size?

KEY TAKEAWAY: Suitability is about fit — the ADT/pattern that best matches the problem’s operations, scale, and correctness requirements.

Problem Context Examples

Context 1: Network Routing

Problem: Find the shortest route between two cities in a road network.

• ADT choice: Graph (cities = vertices, roads = weighted edges) + Priority Queue (greedy selection)
• Design pattern: Greedy (Dijkstra’s algorithm)
• Justification: Road networks have non-negative distances; Dijkstra’s is optimal and efficient at $O((V+E)\log V)$

Context 2: Scheduling Jobs by Priority

Problem: Process jobs in order of urgency; new jobs arrive continuously.

• ADT choice: Priority Queue
• Justification: insert and removeMin in $O(\log n)$; jobs retrieved by priority, not arrival order
• Design pattern: Greedy (always process most urgent first)

Context 3: Web Crawler

Problem: Visit all reachable web pages from a starting URL.

• ADT choice: Queue (for BFS) + Set (track visited pages)
• Design pattern: BFS graph traversal
• Justification: BFS explores pages level by level; Set prevents revisiting

Context 4: Solving a Maze

Problem: Find a path from entrance to exit in a maze.

• ADT choice: Stack (for DFS/backtracking)
• Design pattern: Backtracking / DFS
• Justification: DFS naturally follows one path until stuck, then backtracks

Context 5: Word Frequency Analysis

Problem: Count how many times each word appears in a document.

• ADT choice: Dictionary (word → count)
• Justification: $O(1)$ average lookup and update by key; perfect for key-value mapping

Complexity as a Suitability Criterion

When multiple ADTs/patterns could work, complexity is the tiebreaker:

EXAM TIP: When justifying suitability, mention both the functional fit (the ADT supports the required operations) and the efficiency (the complexity is appropriate for the problem’s scale).

Common Justification Template

“The [ADT] is suitable because the problem requires [operation], which the [ADT] supports in [complexity]. The [design pattern] is appropriate because [property of the problem] means that [why the pattern applies].”

Example: “The priority queue is suitable because the problem requires repeatedly finding the minimum-cost edge, which the priority queue supports in $O(\log n)$. The greedy pattern is appropriate because the cut property guarantees that choosing the minimum edge at each step produces the global minimum spanning tree.”

VCAA FOCUS: Justification must be specific to the problem scenario — generic statements like “it’s efficient” are insufficient. Tie the ADT’s operations directly to the problem’s requirements.