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.