Combining ADTs to Meet Complex Problem Requirements

Why Combine ADTs?

Real-world problems are rarely modelled by a single ADT. Complex information has multiple dimensions that are best captured by combining multiple ADTs, each handling a different aspect of the data.

KEY TAKEAWAY: Complex problems require composite data models. The skill is identifying which aspects of the problem each ADT models and how they interact.

Principles of Combining ADTs

1. One ADT per concern: Each ADT should model one clear aspect of the problem
2. Relationships between ADTs: How the ADTs reference each other (e.g., a Graph whose node values are Dictionaries)
3. Efficiency: The combined structure must support the required operations efficiently
4. Justified by the problem: Each ADT in the combination should be necessary

Example 1: Social Network with Attributes

Problem: Represent a social network where each person has attributes (name, age, location) and connections to friends.

Combination:
- Graph ADT: Each node = a person; edges = friendships (undirected)
- Dictionary ADT: Each node value = dictionary mapping attribute names to values

graph = {
  'Alice': [('Bob', 1), ('Carol', 1)],
  'Bob': [('Alice', 1)],
  'Carol': [('Alice', 1)]
}
person_data = {
  'Alice': {'age': 25, 'city': 'Melbourne'},
  'Bob':   {'age': 30, 'city': 'Sydney'},
  'Carol': {'age': 22, 'city': 'Melbourne'}
}

Example 2: Dijkstra’s Algorithm — Multiple ADTs

Dijkstra’s algorithm itself uses a combination of ADTs:
- Graph ADT: Store the network (vertices, weighted edges)
- Priority Queue ADT: Always select the closest unvisited vertex
- Dictionary ADT: Store known shortest distances from source
- Set ADT: Track which vertices have been finalised

Each ADT serves a specific role in the algorithm — none could replace another.

Example 3: Task Scheduler with Dependencies

Problem: Schedule tasks where some tasks must complete before others, and tasks have priorities.

Combination:
- Graph ADT (DAG): Model dependencies (task A → task B means A must precede B)
- Priority Queue ADT: Among tasks with all prerequisites met, process highest priority first
- Set ADT: Track which tasks have been completed

Example 4: Hospital Emergency System

Problem: Manage patients arriving at an emergency department, with triage priority, patient records, and wait-time tracking.

Combination:
- Priority Queue ADT: Triage patients by urgency
- Dictionary ADT: Map patient ID → patient record (name, diagnosis, medications)
- Queue ADT: Patients at the same priority level are seen in arrival order
- List ADT: Ordered history of treatments for each patient

Describing Complex ADT Combinations

When communicating a combined ADT design, specify:
1. Which ADTs are used
2. What each ADT represents in the problem domain
3. How they interact (what connects them)
4. Why each ADT was chosen (what operations it supports)

EXAM TIP: VCAA exam questions may ask you to “describe how complex information can be represented by a combination of ADTs.” Structure your answer: (1) list each ADT used, (2) state what it models, (3) explain how they connect, (4) mention key operations.